題目資訊

• 題目編號: 2140
• 題目連結: Solving Questions With Brainpower
• 主題: Array, Dynamic Programming

題目敘述

你被給予一個0-索引的2D整數陣列 questions，其中 $questions[i] = [points_i, brainpower_i]$。

此陣列描述了一場考試的題目，你需要依序處理這些題目（即從題目 0 開始），並決定是否解答或是跳過每一個題目。解答題目 i 會讓你獲得 $points_i$ 分，但你將無法解答接下來的 $brainpower_i$ 題。如果跳過題目 i，你就可以對下一個題目做出決定。

• 例如，給定 questions = [[3, 2], [4, 3], [4, 4], [2, 5]]：
  • 如果解答題目 0，你將獲得 3 分，但將無法解答題目 1 和 2。
  • 如果相反地，跳過題目 0 並解答題目 1，你將獲得 4 分，但將無法解答題目 2 和 3。

返回你能夠在考試中獲得的最大分數。

範例 1:

輸入: questions = [[3,2],[4,3],[4,4],[2,5]]
輸出: 5
解釋: 最大分數可以通過解答題目 0 和 3 來獲得。
- 解答題目 0: 獲得 3 分，將無法解答接下來的 2 個題目
- 無法解答題目 1 和 2
- 解答題目 3: 獲得 2 分
總獲得分數: 3 + 2 = 5。沒有其他方法可以獲得 5 分或更多。

範例 2:

輸入: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
輸出: 7
解釋: 最大分數可以通過解答題目 1 和 4 來獲得。
- 跳過題目 0
- 解答題目 1: 獲得 2 分，將無法解答接下來的 2 個題目
- 無法解答題目 2 和 3
- 解答題目 4: 獲得 5 分
總獲得分數: 2 + 5 = 7。沒有其他方法可以獲得 7 分或更多。

限制條件:

• $1 \leq questions.length \leq 10^5$
• $questions[i].length == 2$
• $1 \leq points_i, brainpower_i \leq 10^5$

直覺

這個問題可以使用動態規劃來解決。核心思想是對於每一個題目，決定是解答還是跳過，以使獲得的總分數最大化。透過採用動態規劃的模式，我們可以系統地評估每一步的潛在結果，從後往前逐步分析。

解法

為了解決這個問題，我們採用動態規劃的方法，定義一個動態規劃陣列 dp，其中 dp[i] 表示從第 i 個問題開始所能獲得的最大分數。

1. 初始化：我們將動態規劃陣列初始化為 dp[i] = 0，對於所有的 i。除了最後一個問題，它被設為自身的得分值，因為後面已經沒有其他問題可以影響其選擇。

2. 逆向迭代：我們以逆序遍歷問題，從倒數第二題到第一題。這樣的逆向遍歷允許我們基於後續問題做出的最佳決策來決定每個問題的最佳策略。

3. 決策製作：對於每一個問題 i：

   • 我們首先假設跳過這個問題，因此繼承下一個問題的最大分數：dp[i] = dp[i + 1]。
   • 如果選擇解答當前問題，我們將獲得 questions[i][0] 分。在解答後，我們必須跳過接下來的 questions[i][1] 個問題。因此，我們的分數將成為 questions[i][0] + dp[i + questions[i][1] + 1]，如果這個索引在範圍內。
   • 我們然後更新 dp[i] 為解答或跳過當前問題的最大值：dp[i] = max(dp[i], questions[i][0] + future_points)，其中 future_points 是 dp[i + questions[i][1] + 1]，如果索引有效，否則為 0。

4. 結果擷取：在處理完所有問題後，dp[0] 將包含從第一個問題開始所能獲得的最大分數，這就是所需的結果。

這個方法有效地在 $O(n)$ 的時間複雜度內計算出解決方案，其中 $n$ 是問題數量，這使其適合題目限制中定義的大規模輸入。

程式碼

C++

class Solution {
public:
    // 函數以返回兩個數中的最大值
    long long max(long long a, long long b) { 
        return a > b ? a : b; 
    }

    // 函數計算可以獲得的最多分數
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();  // 獲取問題的數量
        vector<long long> dp(n, 0);  // DP陣列，用於存儲每道問題的最大分數

        // 基本情況：最後一題的最大分數即為其本身的分數
        dp[n-1] = questions[n-1][0];

        // 反向遍歷所有問題
        for (int i = n - 2; i >= 0; i--) {
            dp[i] = dp[i + 1];  // 初始假設跳過當前問題

            // 檢查解決當前問題是否能帶來更多分數
            if (i + questions[i][1] + 1 < n) {
                dp[i] = max(dp[i], questions[i][0] + dp[i + questions[i][1] + 1]);
            } else {
                dp[i] = max(dp[i], questions[i][0]);
            }
        }

        // 答案是我們從第一題開始可以獲得的最大分數
        return dp[0];
    }
};

Python

class Solution:
    # 函數用於返回兩個數中的最大值
    def max(self, a, b):
        return a if a > b else b

    # 函數用於計算可以獲得的最多分數
    def mostPoints(self, questions):
        n = len(questions)  # 獲取問題的數量
        dp = [0] * n  # DP陣列用於儲存每個問題可以獲得的最大分數

        # 基本情況: 最後一個問題的最大分數就是它本身的分數
        dp[n - 1] = questions[n - 1][0]

        # 反向遍歷問題
        for i in range(n - 2, -1, -1):
            dp[i] = dp[i + 1]  # 初始假設跳過當前問題

            # 檢查解決當前問題是否能獲得更多分數
            if i + questions[i][1] + 1 < n:
                dp[i] = self.max(dp[i], questions[i][0] + dp[i + questions[i][1] + 1])
            else:
                dp[i] = self.max(dp[i], questions[i][0])

        # 答案是我們從第一個問題可以獲得的最大分數
        return dp[0]

複雜度分析

• 時間複雜度: $O(n)$
  時間複雜度為 $O(n)$，因為此演算法從後向前迭代整個問題列表一次，並且對於每個問題執行恆定數量的操作。因此，時間複雜度與問題數量 $n$ 呈線性關係。
• 空間複雜度: $O(n)$
  空間複雜度為 $O(n)$，因為我們使用了一個動態規劃陣列 dp 來儲存從每個問題開始可以獲得的最大分數。該陣列的長度等於問題的數量 $n$，因此需要線性的空間需求。