Pattern visualizer
Frog Jump
The frog's next move depends on the SIZE of its last jump, not just where it is standing — so the state is (stone, incoming jump k), not just stone. Track, for every stone, the set of jump sizes that can legally land on it. Starting from dp[0][0] = true, push each known jump size k forward as k-1, k, and k+1 onto whichever stone sits that far ahead. The last stone is reachable exactly when its set ends up non-empty. Animated on: stones = [0,1,3,5,6,8,12,17] — jump k units, then k-1, k, or k+1 next. Can the frog reach the last stone?.
dp[i][k] = stone i is reachable on a jump of exactly k units
dp[i][k] = the frog can stand on stone i having just jumped k units
The frog starts on stone 0 with no prior jump, so dp[0][0] is the one seed cell — every reachable cell downstream is propagated from here.
1FUNCTION canCross(stones):2 dp[0][0] <- TRUE3 FOR i FROM 0 TO LENGTH(stones) - 1:4 FOR EACH k IN dp[i]:5 IF k - 1 > 0 AND stones[i] + (k - 1) IS a stone AT j: dp[j][k-1] <- TRUE6 IF k > 0 AND stones[i] + k IS a stone AT j: dp[j][k] <- TRUE7 IF stones[i] + (k + 1) IS a stone AT j: dp[j][k+1] <- TRUE8 RETURN dp[LAST] IS NOT EMPTY
← / → step · space play · Home restart