LeetCode:Jump Game

LeetCode: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.

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

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

兩種思路，從前往後和從後往前，看能夠到達的最遠的點。

實現代碼：

class Solution {
public:
    bool canJump(int A[], int n) {
        int reach=0;
        int i=0;
        for(;i

或者從後往前推：
 
 
class Solution {
public:
    bool canJump(int A[], int n) {
        int last=n-1,i,j;
        for(i=n-2;i>=0;i--)
        {
            if(A[i]+i>=last)
                last=i;
        }
        return last<=0;
    }
};