题解 | #跳跃游戏(三)#

此题与leetcode跳跃游戏2为同一题，在此给出leetcode的链接。
leetcode题目链接

这题要 求的是 最少次数。
我们贪心的去思考，只要我们每次跳的尽可能远，就能保证跳跃次数尽可能少。
那是不是我们直接每次都跳最远的距离，就行了吗？
很明显不是。
因为如果存在如下情况 4 10 1 1 1 1 1 1 1
我们直接跳到10，就可以到达结束点了，但是每次跳最远，反而会更慢。

这是因为在第一个点可到达的范围内，存在某点x，它比这块范围内的其他点能到达的区域都更远。
这个点才是我们该跳到的点。

如果我们不选择x，而选择它前面或者后面的点 others。
那么对于它能到达的最远点j, others要达到这个点至少需要2次以上的跳跃了。（当然还可以到不了）

这里想完了之后再去想想何时更新这个最远距离。
答案是 第一个点的最远点，因为这样才能保证我们每次都正确地选取了 x。

依照上述思路，注意一下边界情况，就能写出代码了。

#include 
int main() {
    //读数
    int n;
    scanf("%d", &n);
    int nums[n];
    for(int i = 0; i < n; ++i) {
        scanf("%d", &nums[i]);
    }
    // 边界判断
    if(n == 0) {
        printf("-1");
        return 0;
    }
    if(n == 1) {
        printf("0");
        return 0;
    }
    //  核心逻辑
    int maxLength = nums[0], currentLength = nums[0], c = 0;
    for(int i = 0; i < n; ++i) {
        if(nums[i] + i > maxLength) {
            maxLength = n-1 < nums[i] + i ? n-1 : nums[i] + i;
        }
        if(i == currentLength) {
            currentLength = maxLength;
            ++c;
        }
    }
    //输出
    if(currentLength >= n-1) {
        printf("%d", c);
    }  else {
        printf("-1");
    }
    return 0;
}