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 earn3
points but you will be unable to solve questions1
and2
. - If instead, question
0
is skipped and question1
is solved, you will earn4
points but you will be unable to solve questions2
and3
.
- If question
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
Solution: DP
A more general version of 花花酱 LeetCode 198. House Robber
dp[i] := max points by solving questions[i:n].
dp[i] = max(dp[i + b + 1] + points[i] /* solve */ , dp[i+1] /* skip */)
ans = dp[0]
Time complexity: O(n)
Space complexity: O(n)
Python3
1 2 3 4 5 6 7 8 9 10 11 |
# Author: Huahua class Solution: def mostPoints(self, questions: List[List[int]]) -> int: n = len(questions) @cache def dp(i: int) -> int: if i >= n: return 0 p, b = questions[i] return max(p + dp(i + b + 1), dp(i + 1)) return dp(0) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment