用取捨DP來考高分 Solving Questions With Brainpower_Leetcode #2140

Ben Mullins on Unsplash

題目敘述 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特訓班目錄 和 學習路徑