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;

    }

};