LeetCode 2140 Solving Questions With Brainpower

LeetCode

You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].

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 pointsi points but you will be unable to solve each of the next brainpoweri 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:

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.

Example 2:

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.

Constraints: 1 <= questions.length <= 105
questions[i].length == 2 1 <= pointsi, brainpoweri <= 105

题目大意：

(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

注意事项：

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

Python代码：

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代码：

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)

算法分析：

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