首页 > 代码库 > leetcode第一刷_Jump Game II

leetcode第一刷_Jump Game II

要求最小的步数,是不是很容易想到用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];
    }
};