KK's blog

每天积累多一些

0%

LeetCode 2140 Solving Questions With Brainpower

Posted on Edited on Disqus:

LeetCode

<div>

You are given a 0-indexed 2D integer array questions where questions[i] = [points<sub>i</sub>, brainpower<sub>i</sub>].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you points<sub>i</sub> points but you will be unable to solve each of the next brainpower<sub>i</sub> questions. If you skip question i, you get to make the decision on the next question.

  • For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
    • If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
    • If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return the maximum points you can earn for the exam.

Example 1:

<pre>Input: questions = [[3,2],[4,3],[4,4],[2,5]] Output: 5 Explanation: The maximum points can be earned by solving questions 0 and 3.

  • Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
  • Unable to solve questions 1 and 2
  • Solve question 3: Earn 2 points Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points. </pre>

Example 2:

<pre>Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]] Output: 7 Explanation: The maximum points can be earned by solving questions 1 and 4.

  • Skip question 0
  • Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
  • Unable to solve questions 2 and 3
  • Solve question 4: Earn 5 points Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points. </pre>

Constraints:

  • 1 <= questions.length <= 10<sup>5</sup>
  • questions[i].length == 2
  • 1 <= points<sub>i</sub>, brainpower<sub>i</sub> <= 10<sup>5</sup>

</div>

题目大意：

(points, brainpower)解决一个问题得到points分，但是接下来的brainpower个问题都不能回答。求最大分数

一维DP解题思路(推荐)：

类似于LeetCode 198 House Robber，但此不再是固定的相邻不能偷，而是动态多个不能偷。
这题求最值，且数组有序访问，暴力法是多项式复杂度，所以考虑用DP。详见解法二。考虑优化算法二
首先考虑用累计dp，但是即使这样，由于前n-1个问题每个不能回答的范围都不同，并不能容易由第n-1个累计DP获得dp[n]
巧妙地利用从后往前计算，这样dp值不能回答范围包含在了已经计算的dp值中，如计算dp[3] <- dp[i + questions[3][1] + 1] + questions[3][0], 后者最大的话，当前结果也是最大，符合归纳条件。

解题步骤：

N/A

注意事项：

  1. 如哈雷彗星，限制条件是向后，所以从后往前计算
  2. 用累计DP： F[i] = max(F[i + 1], f)

Python代码：

1
2
3
4
5
6
7
8
def mostPoints(self, questions: List[List[int]]) -> int:
	dp = [0] * (len(questions) + 1)
	for i in range(len(dp) - 2, -1, -1):
		next_val = 0
		if i + questions[i][1] + 1 < len(dp):
			next_val = dp[i + questions[i][1] + 1]
		dp[i] = max(dp[i + 1], questions[i][0] + next_val)
	return dp[0]

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

二维DP算法II解题思路：

一开始我的思路是比较直接，此算法TLE。 dp[i]为以回答了第i个问题及之前的问题所得分数。递归式为：

1
dp[i] = max(dp[j] + questions[i][0]) if j + questions[j][1] < i, 0 <= j < i

Python代码：

1
2
3
4
5
6
7
8
def mostPoints2(self, questions: List[List[int]]) -> int:
	dp = [0] * len(questions)
	for i in range(len(dp)):
		dp[i] = questions[i][0]
		for j in range(i):
			if j + questions[j][1] < i:
				dp[i] = max(dp[i], dp[j] + questions[i][0])
	return max(dp)

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>，空间复杂度O(n)。

Free mock interview