LeetCode 筆記 - 45. Jump Game II

Posted on

題目在此 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]

也許你也會想看看