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

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution:

(1) DP

我犯了两个错误，一个是J 不一定要正好可以跳到i 点，也可以是大于等于i点， 第二个错误是，使用了F[j] + j >= i, 应该是A[j] + j >= i

class Solution:
    # @param A, a list of integers
    # @return a boolean
    def canJump(self, A):
        n = len(A)
        F = [False for i in range(n)]

        F[0] = True


        for i in range(1, n):
            for j in range(0, i):
                if F[j] and A[j] + j >= i:
                    F[i] = True
                    break

        return F[-1]

(2) 贪心法

通过循环，确认每一个点的最远能跳到的距离，然后不停的更新最远距离，最后如果能跳到最后一个点，说明可以跳到。

class Solution:
    # @param A, a list of integers
    # @return a boolean
    def canJump(self, A):
        ans = 0
        n = len(A)
        for i in range(0, n - 1):
            ans = max(ans, A[i] + i)
            if ans <= i: # 最大的跳跃步数必须大于当前的索引，这样才可以向后跳动。
                return False
        return True