LeetCode 筆記 - 45. Jump Game II

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

相關文章