给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
class Solution: def canJump1(self, nums): m = 0 for i, num in enumerate(nums): if i > m: return False m = max(m, i + num) return True class Solution: def canJump2(self, nums): """ :type nums: List[int] :rtype: bool """ nums_len = len(nums) return self._canJump(nums, nums_len - 1) def _canJump(self, nums, index): if index == 0: return True for i in range(index): if nums[i] + i >= index and self._canJump(nums, i): return True return False class Solution: def canJump3(self, nums): n=len(nums) dp=[False]*len(nums) dp[-1]=True index=len(nums)-1 for i in range(len(nums)-2,-1,-1): if index-i<=nums[i]: index=i dp[index]=True step=0 end=0 max_=0 for i in range(n): if max_>=i: max_=max(max_,i+nums[i]) if i==end: end=max_ step+=1 res=[] newres=[] # return dp print(dp) print('*'*10) def dfs(tmp,i): if i<=0: if dp[0] is True: newtemp=['o']*n for t in tmp[::-1]: newtemp[t]='x' res.append(newtemp) newres.append(tmp[::-1]) else: return if not dp[i]: return for k in range(i): if nums[k]+k>=i: dfs(tmp+[k],k) dfs([n-1],n-1) return res,newres,step x=Solution() arr=[2,3,1,1,4] m,n,step=x.canJump(arr) for y in range(len(m)): print(m[y]) print(n[y]) print('*'*10) print(step)
