🔗 🟡 2140. Solving Questions With Brainpower 1709

tags: `Weekly Contest 276` `陣列(Array)` `動態規劃(Dynamic Programming)`

題意

給定一個下標從 $0$ 開始的二維整數陣列 $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$ 題。

請返回你在這場考試中能獲得的最高分數。

思路：選或不選

方法一：Top-Down

首先題目中已經給了提示，對於每個問題都有兩種選擇，解答或跳過。

因此我們可以考慮使用動態規劃(Dynamic Programming) 來解決這個問題。令 $f(i)$ 表示從第 $i$ 個問題開始考慮能獲得的最大分數，那麼對於第 $i$ 個問題，我們有兩種選擇：

跳過第 $i$ 個問題，那麼我們可以繼續考慮第 $i+1$ 個問題，因此 $f(i) = f(i+1)$ 。
解答第 $i$ 個問題，那麼我們可以獲得 $points_i$ 分，但是不能解答後續 $brainpower_i$ 個問題，因此 $f(i) = points_i + f(i+brainpower_i+1)$ 。

此外，我們還需考慮邊界條件，如果 $i \geq n$ 時，我們就無法再解答任何問題，因此此時 $f(i) = 0$ 。

因此我們可以得到狀態轉移方程如下：

$f(i) = \begin{cases} 0 & \text{if } i \geq n \\ max(f(i+1), points_i + f(i+brainpower_i+1)) & \text{otherwise} \end{cases}$

得到上述直接使用自頂向下(Top-Down) 的記憶化搜尋(Memoization) 來實現即可，最後返回 $f(0)$ 即可。

複雜度分析

時間複雜度： $O(n)$ $O (n)$ ，其中 $n$ $n$ 是問題的數量。
- 每個問題只會被計算一次，因此時間複雜度為線性。
空間複雜度： $O(n)$ $O (n)$ 。
- 遞歸的深度最多為 $n$ ，因此空間複雜度為線性，為遞迴時的堆疊空間。

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        @cache
        def f(i: int) -> int: # 從第 i 個問題開始考慮最多可以獲得多少分數
            if i >= n:
                return 0
            res1 = f(i + 1) # 不選第 i 個問題
            res2 = questions[i][0] + f(i + questions[i][1] + 1) # 選第 i 個問題
            return max(res1, res2)
        return f(0)

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();
        vector<long long> memo(n, -1);
        // 這題直接寫 lambda 會 TLE，需要用 auto && f
        auto f = [&](auto && f, int i) -> long long {
            if (i >= n) return 0;
            long long & res = memo[i];
            if (res != -1) return res;
            long long res1 = f(f, i + 1);
            long long res2 = questions[i][0] + f(f, i + questions[i][1] + 1);
            return res = max(res1, res2);
        };
        return f(f, 0);
    }
};

方法二：Bottom-Up

同樣地，我們也可以使用自底向上(Bottom-Up) 的方式來實現這個問題。

令 $f[i]$ 表示從第 $i$ 個問題開始考慮能獲得的最大分數，那麼我們可以使用長度為 $n+1$ 的陣列來存儲每一狀態的最佳得分，並從最後一個狀態開始反向計算，逐步計算每一狀態的最佳得分。

這裡多使用了一個狀態 $f[n]$ 來表示當沒有題目可做時的得分，這樣可以避免在計算時進行額外的判斷，只需要在轉移時對 $n$ 取 $\min$ 即可。

最後同樣返回 $f[0]$ 即可。

複雜度分析

時間複雜度： $O(n)$ $O (n)$ ，其中 $n$ $n$ 是問題的數量。
- 每個問題只會被計算一次，因此時間複雜度為線性。
空間複雜度： $O(n)$ $O (n)$ 。
- 需要使用一個長度為 $n+1$ 的陣列來存儲每一狀態的最佳得分，因此空間複雜度為線性。

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        f = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            f[i] = max(f[i + 1], questions[i][0] + f[min(i + questions[i][1] + 1, n)])
        return f[0]

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();
        vector<long long> f(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            f[i] = max(f[i+1], questions[i][0] + f[min(i + questions[i][1] + 1, n)]);
        }
        return f[0];
    }
};