跳跃游戏

有n块石头分别在 $0, 1, \dots, n-1$ 的位置，一只青蛙在石头0，想跳到石头n - 1。如果青蛙在第i块石头上，每块石头的元素表示可以跳跃的最长距离。问青蛙能否跳到石头n - 1。

示例1

输入：s = [2, 3, 1, 1, 4]

输出：True

解释：可以先跳1步，从石头0达到石头1，然后再从石头1跳3步到达目标。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

示例2

输入：s = [3, 2, 1, 0, 4]

输出：False

解释：从可达的石头出发，最远只能到达石头3，但该石头的最大跳跃长度是0，所以永远不可能到达目标。

如果青蛙能跳到最后一块石头n - 1，那么它一定是从石头i跳过来的（i < n - 1）。

这需要两个条件同时满足：

青蛙可以跳到石头i。
最后一跳不能超过可以跳跃的最大距离。

题目

石头i的最大跳距很大，为什么不能直接认定后面的石头可达？

那么问题转化为了青蛙能否跳到石头i。假设f[j]表示青蛙能否跳到石头j，可以得出转移方程：

f[j] = OR_{0 \le i < j}(f[i]\ AND\ i + a[i] \ge j)

$f[j]$ ：青蛙能否跳到石头 $j$ 。
$OR_{0 \le i < j}$ ：枚举上一个跳到的石头 $i$ 。
$f[i]$ ：青蛙能否跳到石头 $i$ 。
$a[i]$ ：最后一步的距离不能超过 $a_i$ 。

初始条件为f[0] = True，因为青蛙一开始就在石头0。

跳跃游戏

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdbool.h>

bool can_jump(int *stones, int n) {
    bool can_jump[n];
    can_jump[0] = true;

    for (int j = 1; j < n; j++) {
        can_jump[j] = false;
        for (int i = 0; i < j; i++) {
            if (can_jump[i] && i + stones[i] >= j) {
                can_jump[j] = true;
                break;
            }
        }
    }
    return can_jump[n - 1];
}

int main(void) {
    int stones[] = {2, 3, 1, 1, 4};
    int n = sizeof(stones) / sizeof(stones[0]);
    if (can_jump(stones, n)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}

输入至少包含一块石头，各元素是非负整数。

题目

[1,0,4]能到达最后一块吗？

石头为[2,0,2,0,1]。逐个求f[j]并记录可达前驱，画出一条到终点的合法路径。说明数值0的石头为什么不一定阻断所有路径。

跳跃游戏

示例1

输入：s = [2, 3, 1, 1, 4]

输出：True

解释：可以先跳1步，从石头0达到石头1，然后再从石头1跳3步到达目标。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

示例2

输入：s = [3, 2, 1, 0, 4]

输出：False

解释：从可达的石头出发，最远只能到达石头3，但该石头的最大跳跃长度是0，所以永远不可能到达目标。

如果青蛙能跳到最后一块石头n - 1，那么它一定是从石头i跳过来的（i < n - 1）。

这需要两个条件同时满足：

青蛙可以跳到石头i。
最后一跳不能超过可以跳跃的最大距离。

题目

石头i的最大跳距很大，为什么不能直接认定后面的石头可达？

那么问题转化为了青蛙能否跳到石头i。假设f[j]表示青蛙能否跳到石头j，可以得出转移方程：

f[j] = OR_{0 \le i < j}(f[i]\ AND\ i + a[i] \ge j)

$f[j]$ ：青蛙能否跳到石头 $j$ 。
$OR_{0 \le i < j}$ ：枚举上一个跳到的石头 $i$ 。
$f[i]$ ：青蛙能否跳到石头 $i$ 。
$a[i]$ ：最后一步的距离不能超过 $a_i$ 。

初始条件为f[0] = True，因为青蛙一开始就在石头0。

跳跃游戏

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdbool.h>

bool can_jump(int *stones, int n) {
    bool can_jump[n];
    can_jump[0] = true;

    for (int j = 1; j < n; j++) {
        can_jump[j] = false;
        for (int i = 0; i < j; i++) {
            if (can_jump[i] && i + stones[i] >= j) {
                can_jump[j] = true;
                break;
            }
        }
    }
    return can_jump[n - 1];
}

int main(void) {
    int stones[] = {2, 3, 1, 1, 4};
    int n = sizeof(stones) / sizeof(stones[0]);
    if (can_jump(stones, n)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}

输入至少包含一块石头，各元素是非负整数。

题目

[1,0,4]能到达最后一块吗？

石头为[2,0,2,0,1]。逐个求f[j]并记录可达前驱，画出一条到终点的合法路径。说明数值0的石头为什么不一定阻断所有路径。

跳跃游戏

跳跃游戏

跳跃游戏：验证可达前驱与距离

知识测验

跳跃游戏：验证可达前驱与距离

知识测验

恢复一条可达跳跃路径

跳跃游戏

跳跃游戏

跳跃游戏：验证可达前驱与距离

知识测验

跳跃游戏：验证可达前驱与距离

知识测验

恢复一条可达跳跃路径