Jump Game

Question

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

Thoughts

另一个array存boolean, 表示是否能够达到element 对每一个element, 如果现在的这个 element可以到达，就将它max jump length以内的所有element的boolean都设为True

Solution

class Solution:
    # @param A, a list of integers
    # @return a boolean
    def canJump(self, A):
        # write your code here
        length = len(A)
        f = [False for i in range(length)]
        f[0] = True
        for i in range(length):
            if f[i] == False:
                continue
            maxLen = A[i]
            for j in range(maxLen + 1):
                if i + j < length:
                    f[i+j] = True

        return f[length-1]