传送门

这题还是一道贪心。（最近LC很喜欢出贪心啊）
因为nums[i]表示在第i个位置时每一步能向前走0~nums[i]的长度，所以若每一步都走的尽量远，最后到达终点时消耗的步数一定最短。（如果这题改成在i位置时只能走nums[i]长度那就变成一道dp了）
所以对于每一步，我们都去选择能够到的最远位置。

在具体实现的时候选择一个循环从左向右遍历。维护一个maxpos值表示当前这个位置能走到的最远位置，并把它更新为边界。当走到边界的时候step++表示走了一步，然后继续更新边界。

值得一提的是，遍历过程仅访问0~n-1个元素，因为在跳到最后一个位置前，border值肯定是大于等于n的，不然就不符合题中“ 总是可以到达数组的最后一个位置”的设定了。如果border==n，step会多加一次。

class Solution {
public:
    int jump(vector<int>& nums) 
    {
        int maxpos = 0, border = 0, step = 0;
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) 
        {
            if (maxpos >= i)//还没走到边界
            {
                //去更新能走到的最大位置
                maxpos = max(maxpos, i + nums[i]);
                //走到了，更新边界
                if (i == border) 
                {
                    border = maxpos;
                    step++;
                }
            }
        }
        return step;
    }
};

感觉这题不配hard。改成dp好像还要更难做一点的样子…