贪心+DP

如果光使用DP的话时间复杂度是$O(N^2)$

对于k来说，我们没必要每次从开头枚举，k能跳到的第一个位置是j的话，若k能跳到不止一个位置，则我们可以一次性将k能跳到的位置全部赋值，并且后面不需要再从开头枚举，这样k是单调递增的。

$ 时间复杂度O(N)，空间复杂度O(N)$

参考文献

lc究极班

AC代码

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 0x3f);
        f[0] = 0;
        int k = 0;
        for (int i = 1 ; i < n ; i ++){
            //k为能跳到i的第一个位置
            while (k < n && k + nums[k] < i) 
                k ++; 
            f[i] = f[k] + 1;
        }
        return f[n - 1];

    }
};