55.贪心：跳跃游戏

image.png

简洁标准解法：动态规划，dp[i]记录nums[i]之前所能到达的最远距离，dp[i] = max(dp[i-1], i + nums[i])，空间优化可以将dp[i]变为dp (k)

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n=len(nums)
        k=0
        for i in range(n):
            if i>k:
                return False
            k=max(k,i+nums[i])
        return True 

本人思路：下一步的位置由：能获得(当前已经走的步数(cur_steps)+当前能走的步数(j<=nums[i])+跳跃过去的那一步能走的步数)的最大值确定，并且判断如果上述的最大值已经超过了跳到最后一步所需的步长，就返回True。

• 记得单独判断只有一步或者为空的情况。

• 犯错记录：忘记在式子中写入当前实际走的步长。

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n=len(nums)-1
        max_steps=0
        cur_steps=0
        i = 0
        if len(nums)<=1:
            return True
        while i<n: 
            nexti=i
            for j in range(1,nums[i]+1):
                if j+nums[i+j] > max_steps:
                    nexti=i+j
                    max_steps=j+nums[i+j]
                if cur_steps+max_steps>=n:
                    return True
            cur_steps+=nexti-i
            max_steps=0   
            if i==nexti:
                return False
            i=nexti
        return False