要求最小的步数，是不是非常easy想到用dp啊？

我一開始的做法是，当找到了一个可以从它延伸到更远的位置，就把这个位置和最远位置的步数都更新一下，结果超时了。

事实上这样不仅是超时的，并且是错误的。由于这段距离里的非常多点，事实上是上一步就能到达的。

事实上应该更新的仅仅有哪些新的可以到达的点，那哪些点是新的能到达的点呢？如果这次可以延伸更远的点是i。它的前进步数是A[i]，上一次可以到达的最远的点是mmax，那新的能到达的点应该是(mmax, i+A[i] ]这个之间的这些位置。时间复杂度一下子变成线性的了。

class Solution {

public:

    int jump(int A[], int n) {

        if(n <= 1)  return 0;

        vector<int> steps(n, INT_MAX);

        steps[0] = 0;

        int mmax=0;

        for(int i=0;i<n-1;i++){

            if(i+A[i]>mmax){

                for(int j=mmax+1;j<=i+A[i]&&j<n;j++)

                    steps[j] = steps[i]+1;

                if(i+A[i]>=n-1)

                    steps[n-1] = min(steps[n-1], steps[i]+1);

                mmax = i+A[i];

            }

        }

        return steps[n-1];

    }

};