題目描述:
給定一個二維陣列 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]。時間複雜度: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 題開始,對每題選擇解或跳過。邏輯直觀但有遞迴開銷。