贪心策略

设f(i)表示到达i位置的最小步数，令last为第一个可以到达i的位置，f[i] = f[last] + 1。

贪心正确性

因为f(i)是单调不减的，因此last之后的点到达i结果只能相同或更差。

class Solution {
public:
    int jump(vector<int>& nums) {
        const int n = nums.size();
        vector<int> f(n);
        int last = 0;
        for(int i = 1; i < n; i++){
            while(last + nums[last] < i) last++;
            f[i] = f[last] + 1;
        }
        return f[n - 1];
    }
};