網(wǎng)站頁面字體設置剛剛地震最新消息今天
2140. 解決智力問題 - 力扣(LeetCode)
這道題是一個典型的 動態(tài)規(guī)劃(Dynamic Programming, DP) 問題,可以使用 自底向上 的方式解決。
思路
-
定義狀態(tài):
設dp[i]
表示從第i
題開始,能獲得的最高分數(shù)。 -
狀態(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])
- 選擇解決第
-
邊界條件:
dp[n] = 0
(當超過最后一題時,得分為0
)。
-
計算順序:
- 我們需要從 后往前 計算
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)。