55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

存在型

解题思路：

1. 确定状态
   开数组的意义 d[n-1]
   确定状态需要两个意识：
   • 最后一步
     从 i 能不能跳到最后一块石头 n-1
     需要满足两个条件：
     （1）青蛙可以跳到石头 i
     （2）最后一步不超过跳跃的最大距离：n - 1 - i < nums[i]
   • 子问题
     青蛙能不能跳到石头 i (i < n - 1)
     d 代表 能不能从 i 跳过来
2. 转移方程
   $d[j] = OR_{0 <= i < j} (d[i] and nums[i] + i >= j)$
3. 初始条件和边界情况
   d[0] = 0
   枚举的情况不会越界
4. 计算顺序
   0 –> n-

时间复杂度 $O(n^2)$, 超过了 leetcode 限制

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        d = [False for _ in range(len(nums))]
        d[0] = True
        for j in range(1,len(nums)):
            for i in range(j):
                if d[i] and nums[i] + i >= j:
                    d[j] = True
                    break
        return d[-1]

优化，从后往前一步一步推导：
Idea is to work backwards from the last index. Keep track of the smallest index that can “jump” to the last index. Check whether the current index can jump to this smallest index.

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