LeetCode 筆記 - 45. Jump Game II

Posted on 標籤
跳跳遊戲系列第二題，尋找抵達終點的最小步數。本文解析如何運用動態規劃（DP）紀錄每個位置的最短步數，透過局部覆蓋範圍的持續更新，在 O(N) 或 O(N^2) 複雜度下收斂出最優路徑，是理解路徑優化問題的經典範例。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 45. Jump Game II

給一個數列，從 index 0 開始，數列裡面代表 i 可以跳幾步
請問最小可以跳到最後的步數？

解題思維

歡迎來跳跳遊戲系列的第二題 ☺
如果沒解過第一題可以看一下 LeetCode 筆記 - 55. Jump Game

這題就真的需要 Dynamic programming 看過去的結果了

在這裡我們可以使用一個 list dp 來記錄 i 的最小步數
所以到了 i 看一下涵蓋範圍，更新一下之後的最小步數的數值即可

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def jump(self, nums: List[int]) -> int:
        
        if (size := len(nums)) == 1:
            return 0
        
        dp = [inf] * size
        dp[0] = 0
        
        for i in range(size):
            max_index = i + nums[i]
            for ii in reversed(range(min(size, max_index + 1))):
                if ii >= size:
                    break
                if dp[ii] != inf:
                    break
                dp[ii] = min(dp[ii], dp[i] + 1)

        return dp[-1]

也許你也會想看看