Jump Game

Jump Game

There are n stones at positions $0,1,\dots,n-1$. A frog starts at stone 0 and wants to reach stone n−1. The value on stone i gives its maximum jump distance. Can the frog reach the last stone?

Example 1

Input: s = [2, 3, 1, 1, 4]

Output: True

Explanation: jump one step from stone 0 to stone 1, then three steps from stone 1 to the destination.

Example 2

Input: s = [3, 2, 1, 0, 4]

Output: False

Explanation: from reachable stones, the frog can get no farther than stone 3. That stone permits a maximum jump of zero, so the target is unreachable.

If the frog reaches stone n−1, it must have jumped from an earlier stone i, with i < n−1.

Two conditions must both hold:

1. Stone i is reachable.

2. The final jump does not exceed its maximum allowed distance.

The problem becomes determining whether stone i is reachable. Let f[j] record whether stone j is reachable:

• f[j]: whether the frog can reach stone j.

• The OR over $0\le i<j$: enumerate the preceding stone i.

• f[i]: whether stone i is reachable.

• a[i]: the final jump must not exceed this distance.

Initially, f[0] = True because the frog starts on stone 0.

Jump game

#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;
}

The input contains at least one stone, with nonnegative integer values.