主題
題目連結：
題目意譯：
你被給定一索引值從 0 開始的二維整數陣列 questions，其中 questions[i] = [pointsi, brainpoweri]。
該陣列代表著一次考試的問題集，在其中你必須依序地處理掉上面的問題（即，從問題 0 開始做）並且對每個問題做出到底是要解掉該問題還是跳過之抉擇。解決問題 i 你將會 pointi 分，但是你將會無法解接下來 brainpoweri 道題目。如果你跳過了問題 i，則你可以繼續到下一個問題進行抉擇。
例如，給定 questions = [[3, 2], [4, 3], [4, 4], [2, 5]]：
如果解決了問題 0，你將會得到 3 分但是你將無法去解問題 1 和 2。
反之如果問題 0 被跳過了，而去解決了問題 1，你將會得到 4 分但是將無法去解問題 2 和 3。
回傳在這個考試中中你可以獲得的最大分數。
限制：
1 ≦ questions.length ≦ 10 ^ 5
questions[i].length == 2
1 ≦ pointsi, brainpoweri ≦ 10 ^ 5
範例測資：
範例 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 分或是更多分數。
解題思維：
本題可以使用動態規劃（Dynamic Programming）的精神解掉。
由於 brainpoweri （即 questions[i][1]，以下以此代稱；同理，pointi 以 questions[i][0] 代稱）的緣故，使得對於問題 i 解掉了之後會有 questions[i][1] 道問題的空窗期。因此這邊我們定義陣列 questions 的長度為 n 以及一陣列 D，其中 D[i] 代表只考慮問題 i ～ n - 1 中最大可以獲得的分數值。
因此可以看到其邊界條件為
D[n - 1] = questions[n - 1][0]
（因為其沒有「下一題」，必定不會有空窗期。因此解了只賺不虧）
而遞迴式可以看到會是
如果 i + questions[i][1] ≧ n，則 D[i] = max(D[i + 1], questions[i][0])
反之，則 D[i] = max(D[i + 1], questions[i][0] + D[i + questions[i][1] + 1])
其中上者是因為空窗期超出了剩下的問題數，因此這個範圍中只能解掉問題 i 本身；而下者則是空窗期「結束」後（因此需要那個「+ 1」）可以繼續選擇要不要解接下來的問題（即問題 i + questions[i][1] + 1 ～ n - 1）。
因此我們從邊界條件往前推到 D[0]，而可以看到此即為所求（問題 0 ~ n - 1 中的最大分數值）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
