Frog Jump

Frog Jump is a classic dynamic-programming problem with a twist: the state is not just where the frog is, but also how it got there. The key move is to remember, for each stone, the set of jump sizes that can reach it.

The slow way first

A plain recursion tries, from the current stone, every allowed next jump and recurses. But the frog can reach the same stone via different last jumps, and each one opens different future moves — so the same (stone, lastJump) pair gets re-explored over and over. Without memoization this is exponential.

The question to ask: what do I need to know to decide my next move? Just the current stone and the size of the jump that landed me here. So the real state is the pair (stone, jump).

The idea: store the jump sizes that reach each stone

Give every stone a set of jump sizes that can land on it. Seed the first stone with jump 0. Then scan stones left to right: for each jump size k that reaches the current stone, try k − 1, k, and k + 1. If that jump is positive and lands on a real stone, add it to that stone's set. At the end, the frog can cross if the last stone's set is non-empty.

Because we only ever push jumps forward onto later stones, a single left-to-right pass fills every set correctly — no recursion needed.

Walk through it

Step through the animation. The from pointer marks the stone we are jumping out of. Each stone shows its current set of reaching jumps underneath. Watch the sets light up forward: stone 0 sends a +1 to stone 1, which sends a +2 to position 3, and so on until position 17 finally receives a jump — proving the crossing is possible.

Pseudocode

pos_set = set of all stone positions          # for O(1) "is there a stone here?"
reach = {position: empty set} for each stone
add jump 0 to reach[first stone]              # seed: we "arrived" on stone 0
for each stone position pos (left to right):
    for each jump size k in reach[pos]:
        for nxt in (k - 1, k, k + 1):
            if nxt > 0 and pos + nxt is a stone:
                add nxt to reach[pos + nxt]
return True if reach[last stone] is non-empty

The Python solution

def can_cross(stones):
    pos_set = set(stones)
    reach = {p: set() for p in stones}
    reach[stones[0]].add(0)
    for pos in stones:
        for k in reach[pos]:
            for nxt in (k - 1, k, k + 1):
                if nxt > 0 and pos + nxt in pos_set:
                    reach[pos + nxt].add(nxt)
    return len(reach[stones[-1]]) > 0

• pos_set lets us answer "is there a stone at this position?" in O(1).
• reach maps each stone position to the set of jump sizes that can land on it.
• We seed reach[stones[0]] with 0 — arriving on the first stone counts as a jump of size 0.
• For each jump k that reaches pos, the three candidate next jumps are k − 1, k, k + 1.
• Line 8 is the filter: the jump must be positive and must land on a real stone.
• Line 9 records the landing jump on the destination stone, so future iterations can build on it.

Complexity

Each of the n stones can store up to O(n) distinct jump sizes, and for each we do a constant amount of work, giving O(n²) time and space. The win over the naive version is that every (stone, jump) state is processed once.

When this pattern shows up

Practice