2140. 解決智力問題 - 力扣（LeetCode）

這道題是一個典型的 動態(tài)規(guī)劃（Dynamic Programming, DP） 問題，可以使用 自底向上 的方式解決。

思路

1. 定義狀態(tài)：
   設 dp[i] 表示從第 i 題開始，能獲得的最高分數(shù)。

2. 狀態(tài)轉移方程：

   • 選擇解決第 i 題：
     • 這樣可以獲得 questions[i][0] 分，并且需要跳過 questions[i][1] 題。
     • 下一次可以從 i + questions[i][1] + 1 題開始，即 dp[i] = questions[i][0] + dp[i + questions[i][1] + 1]。
   • 選擇跳過第 i 題：
     • 這樣可以從 i+1 題開始，即 dp[i] = dp[i+1]。
   • 取兩者的最大值： dp[i]=max?(questions[i][0]+dp[i+questions[i][1]+1],dp[i+1])

3. 邊界條件：

   • dp[n] = 0 （當超過最后一題時，得分為 0）。

4. 計算順序：

   • 我們需要從 后往前 計算 dp[i]，因為 dp[i] 依賴于 dp[i+1] 和 dp[i + questions[i][1] + 1]。

---

代碼實現(xiàn)

from typing import Listdef mostPoints(questions: List[List[int]]) -> int:n = len(questions)dp = [0] * (n + 1)  # dp[i] 表示從第 i 題開始能獲得的最高分for i in range(n - 1, -1, -1):  # 逆序遍歷points, brainpower = questions[i]next_index = i + brainpower + 1  # 下一道可以解的題目dp[i] = max(points + (dp[next_index] if next_index < n else 0), dp[i + 1])return dp[0]

---

復雜度分析

• 時間復雜度：O(n)，我們只需遍歷 questions 一次，每次 O(1) 計算 dp[i]。
• 空間復雜度：O(n)，用于存儲 dp 數(shù)組。

---

示例

輸入

questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
print(mostPoints(questions))

輸出

5

---

優(yōu)化（O(1) 空間）

我們可以只用一個變量來存儲 dp[i+1]，這樣 dp 數(shù)組就不需要額外存儲所有狀態(tài)：

def mostPoints(questions: List[List[int]]) -> int:n = len(questions)next_max = 0  # 相當于 dp[i+1]for i in range(n - 1, -1, -1):points, brainpower = questions[i]next_index = i + brainpower + 1current = max(points + (dp[next_index] if next_index < n else 0), next_max)next_max = current  # 更新 dp[i]return next_max

這樣，我們將 空間復雜度優(yōu)化為 O(1)。