Posted on 2022-12-26 15:12
Uriel 阅读(27)
评论(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]