解題說明
Solving Questions With Brainpower
題目描述：
給定一個二維陣列 questions，其中 questions[i] = [points_i, brainpower_i]。你依序面對每道題，可以選擇解或跳過。若解第 i 題，獲得 points_i 分，但接下來 brainpower_i 題必須跳過。求能獲得的最大分數。
解題思路： 使用反向動態規劃：
- 定義
dp[i]= 從第i題開始（含）能獲得的最大分數。 - 對於第
i題，有兩個選擇：- 跳過：
dp[i] = dp[i+1] - 解題：
dp[i] = points_i + dp[i + brainpower_i + 1]（若超出範圍則為 0）
- 跳過：
dp[i] = max(跳過, 解題)- 從最後一題往前計算，答案為
dp[0]。
C++ 解法
複雜度分析
時間複雜度：O(n) — 從後往前遍歷一次。
空間複雜度：O(n) — DP 陣列大小為 n+1。
虛擬碼
1. Create dp array of size n+1, initialized to 0 2. For i from n-1 down to 0: a. points = questions[i][0], skip = questions[i][1] b. next = i + skip + 1 c. solveScore = points + (next < n ? dp[next] : 0) d. dp[i] = max(dp[i+1], solveScore) 3. Return dp[0]
其他解法
正向 DP O(n)：定義 dp[i] 為考慮前 i 題的最大分數。解第 i 題時更新 dp[i + brainpower_i + 1]。需要維護一個滾動最大值。邏輯略複雜但同樣高效。
記憶化搜尋（Top-down）O(n)：遞迴 + 記憶化，從第 0 題開始，對每題選擇解或跳過。邏輯直觀但有遞迴開銷。
延伸思考
- 如果可以「部分解題」（獲得部分分數且消耗較少 brainpower），DP 狀態應如何修改？
- 如果題目可以任意順序作答（不必依序），問題變成什麼經典問題？
- 此題與「打家劫舍」（House Robber）問題有何結構上的相似性？