用取捨DP來考高分 Solving Questions With Brainpower_Leetcode #2140
題目敘述 Solving Questions With Brainpower
給定一個測驗題陣列，每個欄位都是一個pair，
分別記錄測驗題做完可以得到的分數，和需要的冷卻時間
(也就是會有一段時間不能作答接下來的題目)。
請問在最佳的答題策略下，最多可以獲得多少分數?
測試範例
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.
做第一題獲得3分，必須冷卻2題(第二題、第三題)不能作答。
再做第四題獲得2分，必須冷卻5題不能作答。
最多可以獲得3+2=5分。
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.
做第二題獲得2分，必須冷卻2題(第三題、第四題)不能作答。
再做第五題獲得5分，必須冷卻5題不能作答。
最多可以獲得2+2=7分。
約束條件
Constraints:
1 <= questions.length <= 10^5
測驗題陣列長度介於1~十萬之間。
questions[i].length == 2
每個陣列元素都是一個pair=(答題獲得的分數, 對應的冷卻時間)
1 <= pointsi, brainpoweri<= 10^5
答題獲得的分數, 對應的冷卻時間都介於1~十萬之間。
觀察 每一題也只有兩種情況
回到考試現場，針對每一題也只有兩種情況。
1.解開現在這道題目。
2.跳過現在這道題目。
可以定義DP[i] 代表從第i題 ~ 最後一題，最佳策略下獲得的最高分數。
如果解開這道題目，就會獲得對應的分數，並且會有冷卻時間，之後一段區間內的題目無法作答。
等價的表達式
= questions[i][0] + DP[ 冷卻後可以答的題目編號 ]
= questions[i][0] + DP[ 現在這題 + 冷卻時間 + 1 ]
=questions[i][0] + DP[ i + questions[i][1] + 1 ]
如果跳過這道題目，得0分，但是不會有冷卻時間，可以直接考慮下一題。
等價的表達式
= 得0分 + DP[ 下一題 ]
= 0 + DP[i+1]
= DP[ i+1 ]
對於第i題來說，考量與後續題目的最高取分策略
DP[ i ]
= Max{ 解開現在第i道題目, 跳過第i道題目 }
= Max{ questions[i][0] + DP[ i + questions[i][1] + 1 ], DP[ i+1 ] }
目標是獲得總分越高越好，
所以整張考卷的最佳答題情況
= 從第0題 ~ 最後一題，用最佳策略作答
= DP[0]
演算法 DP動態規劃 + 取(做題)/不取(不做題) 框架
1.定義DP狀態
承接觀察點的思考
定義DP[i] 代表從第i題 ~ 最後一題，最佳策略下獲得的最高分數。
目標是獲得總分越高越好，
所以整張考卷的最佳答題情況
= 從第0題 ~ 最後一題，用最佳策略作答
= DP[0]
2.推導DP狀態轉移關係式
針對第i道題目，也只有兩種情況。
1.解開 第i道題。
2.跳過 第i道題。
如果解開第i道題，就會獲得對應的分數，並且會有冷卻時間，
之後一段區間內的題目無法作答。
等價的表達式
= questions[i][0] + DP[ 冷卻後可以答的題目編號 ]
= questions[i][0] + DP[ 現在這題 + 冷卻時間 + 1 ]
=questions[i][0] + DP[ i + questions[i][1] + 1 ]
如果跳過這道題目，得0分，但是不會有冷卻時間，可以直接考慮下一題。
等價的表達式
= 得0分 + DP[ 下一題 ]
= 0 + DP[i+1]
= DP[ i+1 ]
對於第i題來說，考量與後續題目的最高取分策略
DP[ i ]
= Max{ 解開現在第i道題目, 跳過第i道題目 }
= Max{ questions[i][0] + DP[ i + questions[i][1] + 1 ], DP[ i+1 ] }
3.釐清DP初始狀態
什麼時候是最小規模的問題?
就是整張考券每道題目都考慮過了，這時候後面已經沒有更多題目了。
DP[ i ] = 0 , 如果i已經超過最後一題的題號 (相當於 i >= len(questions) )
程式碼 DP動態規劃 + 取(做題)/不取(不做題) 框架
class Solution:
def mostPoints(self, questions: List[List[int]]) -> int:
# Literal constant to help reader understand without magic number
POINT, SKIP_LENGTH = 0, 1
# DP table
# key: question index
# value: grading points, if we start considering from i
memo = {}
def deal_with(i):
# look-up table
if i in memo:
return memo[i]
# base case aka initial conidtion
if i >= len(questions):
memo[i] = 0
return 0
# general cases
# Either solve or skip current question
solve = questions[i][POINT] + deal_with(i+questions[i][SKIP_LENGTH]+1)
skip = deal_with(i+1 )
# maximize grading points
memo[i] = max( solve, skip )
return memo[i]
# -----------------------------------
return deal_with( i=0 )
複雜度分析
時間複雜度:O( n )
從第一題掃描到最後一題，每個題目考慮一次。
空間複雜度:O(n)
DP table記錄每一題對應的區間(從i題~最後一題)的最高得分。
關鍵知識點 取/不取 的DP框架
針對每一題，其實只有兩種可能:
1.解開 第i道題。
2.跳過 第i道題。
對應到的就是 取(做題)/不取(不做題) 的DP框架，
比較接近的是House Robbery的系列題(每棟房屋要嘛選擇，要嘛跳過)，
強烈建議讀者一起複習，鞏固知識點。
一魚多吃 用DP解House Robbery 打家劫舍問題_Leetcode #198_Leetcode 精選75題解析
化簡無所不在 用學過的DP模型解House Robbery II_Leetcode #213
合縱連橫: 從區間DP理解House Robbery系列題 背後的本質
Reference
[1] Solving Questions With Brainpower - LeetCode
回到DP特訓班目錄 和 學習路徑
你可能也想看
