1. 045

jump-game-ii

2 算法

http://www.cnblogs.com/grandyang/p/4373533.html

DP:O(N)

• cur:当前能到达的最远位置
• pre：之前可以到达的最远位置

3. 代码

class Solution{
public:
    int jump(int A[],int n){
        int res=0,i=0,cur=0;
        while(cur<n-1){
            int pre=cur;
            while(i<=pre){
                cur=max(cur,i+A[i]);
                ++i;
            }
            ++res;
            if(pre==cur)  return -1;
        }

        return res;
    }
};