Can the Frog Cross
Stones sit at given positions along a river, in increasing order, the first at position 0. A frog starts on the first stone and must reach the LAST one, landing only on stones.
The first jump must be exactly 1 unit. After a jump of k units, the next jump
must be k - 1, k or k + 1 units, and must be forwards, so a jump of 0 or less
is not allowed.
Print yes if the last stone can be reached and no otherwise.
The trap is that the position alone is not a state. Landing on a stone says nothing about what is possible next, because the legal jumps depend on HOW you arrived. The same stone reached by a jump of 2 and by a jump of 5 offers entirely different futures.
So the state is the pair:
(current stone, size of the jump that landed here)
and the transitions try the three permitted next sizes, keeping those that land exactly on a stone.
That pairing is the whole lesson. A solution tracking only reachable stones
reports yes on inputs that are impossible, and the failure is invisible on small
cases where every arrival happens to allow the same continuation.
The number of distinct jump sizes at a stone is bounded by the number of stones,
so the state space is O(n^2) and memoising on the pair keeps it polynomial.