题目

有一个包，若干路由器，包在每个路由器处有一个最大跳的步长，问至少几跳能到达终点。每一个数为正整数。

样例：

[2,3,1,1,1]

输出：

解释：

0->1->4

思路1

贪心

class Solution {
public:
    int jump(vector<int>& nums) {
        int ans = 0, cnt = 0, maxn = 0;
        for(int i = 0; i < nums.size() - 1 && i <= cnt; ++i){
            if(nums[i] + i > maxn){
                maxn = nums[i] + i;
            }
            if(maxn >= nums.size() - 1){
                ++ans;
                break;
            }
            if(i == cnt){
                if(cnt != maxn){
                    ++ans;
                }
                cnt = maxn;
            }
        }
        return ans;
    }
};

思路2

数组记录，及数组记录当前最优值，类似于筛法求素数。

const int inf = 0x3f3f3f3f;
int solve(vector<int>v){
    int len = v.size();
    vector<int>dp(len, inf);
    dp[0] = 0;
    for(int i = 0; i < len && dp[i] != inf; ++i){
        for(int j = 1; j <= v[i]; ++j){
            dp[j] = min(dp[j], dp[i] + 1);
        }
    }
    return dp[len - 1] != inf ? dp[len - 1] : -1;
}

思路3

排序，下标为左界，值＋下标为右值，构成区域块，选最少的块覆盖全部区域，覆盖不了等于到不了终点。左值（右值）排序后右值（左值）贪心比较。

总结

刚拿到该题，以为是做过的题，之前做的是能否到达终点。结果忽略了求最少的步数，写完才发现理解错了。然后就慌了，思路就混乱了。就没有然后了。

还是比较适合笔试题，一个人自在，心里有了包袱就自乱阵脚，好水的题都能出错。