Posted on 2022-12-26 15:12
Uriel 閱讀(41)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給出一列數字nums，num[i]表示到達第i個數字時，可以向前走最多nums[i]步，問是否有辦法到達最后一個數字，和45. Jump Game II一樣原理（一個問是否可達，一個問有幾種方式到達），DP
狀態轉移時，記錄目前已到達的最遠距離mx，只需要更新mx+1~i+nums[i]的狀態即可，最后檢查dp[-1]是否大于0
1 #55
2 #Runtime: 538 ms (Beats 72.82%)
3 #Memory: 14.7 MB (Beats 10.75%)
4
5 class Solution(object):
6 def canJump(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: bool
10 """
11 mx = 0
12 dp = [0] * len(nums)
13 for i in range(len(nums)):
14 for j in range(mx + 1, min(i + nums[i] + 1, len(nums))):
15 if not i or dp[i]:
16 dp[j] = dp[i] + 1
17 mx = max(mx, nums[i] + i)
18 return len(nums) == 1 or dp[-1]