55.|55. Jump Game

dynamic programmingclass Solution(object): def canJump(self, nums): """ :type nums: List[int] :rtype: bool """ l=len(nums) if l==1 :return True d=[0 for i in xrange(l)] d[0]=nums[0] if d[0]==0: return False for i in xrange(1,l): if nums[i]==0 and d[i-1]<=i:return False d[i]=max(d[i-1],i+nums[i]) if d[i]>=l-1: return True return False

class Solution(object): def canJump(self, nums): """ :type nums: List[int] :rtype: bool """ reachable=0 for i, length in enumerate(nums): if i>reachable: break reachable=max(reachable,i+length) return reachable>=len(nums)-1

    推荐阅读