Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数字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]


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理