学步园

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.

思路：

直接考虑的方式是这样的，最后一个元素标记为true，然后依次考察之前的元素，每个之前的元素如果在前进范围内有标记为true的元素，则标记为true，否则标记为false。这样直到第一个元素，返回第一个元素的值。

题解：

class Solution {
public:
    bool canJump(int A[], int n) {
        // store the maximum index can be reached from the i-th index
        vector<bool> reachable(n);
        reachable[n-1] = true;  // it can always reach itself
        
        auto reach_forward=[&reachable,n](const int index, const int dist) -> bool {
            for(int fwd = index+1; fwd <= min(dist, n-1); ++fwd)
                if (reachable[fwd]) 
                    return true;
            return false;
        };
        
        // reverse iterate every previous element 
        for(int ri = n-2; ri>=0; --ri)
            reachable[ri]=reach_forward(ri, A[ri]);
            
        return reachable[0];
    }
};

思路：

上述题解能够给出正确的解，但是时间复杂度为O(n^2)。如果有O(n)的解法更好。

从正向考察每个元素，记能到达的最远元素为so_far。如果so_far>=n-1，说明可以到达最终元素，如果已经考察到记为so_far的元素，仍不能令so_far >= n-1，说明无法到达最终元素。

题解：

class Solution {
public:
    bool canJump(int A[], int n) {
        // store the farthest element can be reached
        int so_far = 0;
        
        for(int iter=0; iter<=so_far; ++iter)
            if ( (so_far = max(so_far, A[iter] + iter)) >= n-1 )
                return true;
        return false;
    }
};