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.

先想到了动态规划，不过可惜大数据没有过，是一个从25000到0的递减一的数组，想试试贪心。

动态规划：

class Solution {public:    bool canJump(int A[], int n) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        bool B[n];        B[n-1] = true;        for(int i = n-2;i>=0;i--)        {            int x = A[i];            B[i] = false;            if(i+x>n-1)                B[i] = true;            else            while(x!=0&&!B[i])            {                if(B[i+x]==true)                B[i]=true;                x--;            }        }        return B[0];    }};

贪心：

class Solution {private: map
     
       record;    public:    bool canJump(int A[], int n) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        record.clear();        for(int i = 0;i
      
       =n-1)        {            record[i] = true;            return true;        }        else if(A[i]==0)        {            record[i] = false;            return false;        }        else        {            map
       
        ::iterator iter= record.find(i);            if(iter!=record.end())            return record[i];            else            {                return Jump(A,n,A[i]+i);            }        }    }};