力扣刷题--跳跃游戏II（c语言实现）

1.题目   

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

2. 解题思路

拿示例1来看，从数组的第 0 个位置开始跳，跳的距离小于等于数组上对应的数。求出跳到最后个位置需要的最短步数。比如上图中的第 0 个位置是 2，那么可以跳 1 个距离，或者 2 个距离，我们选择跳 1 个距离，就跳到了第 1 个位置，也就是 3 上。然后我们可以跳 1，2，3 个距离，我们选择跳 3 个距离，就直接到最后了。所以总共需要 2 步。

这道题算是一个经典的贪心法，我们每次在可跳范围内选择可以使得跳的更远的位置。也就是每次找局部最优解，最后找全局最优解。

如下图，开始的位置是 2，可跳的范围是橙色的。然后因为 3 可以跳的更远，所以跳到 3 的位置。

如下图，然后现在的位置就是 3 了，能跳的范围是橙色的，然后因为 4 可以跳的更远，所以下次跳到 4 的位置。

写代码的话，我们用 end 表示当前能跳的边界，对于上边第一个图的橙色 1，第二个图中就是橙色的 4，遍历数组的时候，到了边界，我们就重新更新新的边界。

3.以下是代码段

int jump(int* nums, int numsSize){
    int end = 0; //边界
    int maxPosition = 0; //所能跳到的最大位置 
    int steps = 0; //记录跳了多少步骤
    for(int i = 0; i < numsSize - 1; i++){
        //找能跳的最远的
        maxPosition = maxPosition > nums[i] + i ? maxPosition : nums[i] + i;
        //取每一步中的最大可到的位置
        if( i == end){ //遇到边界，就更新边界，并且步数加一
            end = maxPosition;
            steps++;
        }
    }
    return steps;
}