DSA Tracker

Visualize

Frog Jump

dp[i][k] = stone i is reachable on a jump of exactly k units

time O(n^2)space O(n^2)

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.

Details

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?

Problem:Frog JumpHard

dp[i][k] = stone i is reachable on a jump of exactly k units

step 1 / 11

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.

Pseudocode
1FUNCTION canCross(stones):
2  dp[0][0] <- TRUE
3  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] <- TRUE
6      IF k > 0 AND stones[i] + k IS a stone AT j: dp[j][k] <- TRUE
7      IF stones[i] + (k + 1) IS a stone AT j: dp[j][k+1] <- TRUE
8  RETURN dp[LAST] IS NOT EMPTY

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. 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.
  2. From stone 0 (reached on a 0-jump) a 1-jump lands on stone 1: dp[1][1] is now reachable.
  3. From stone 1 (reached on a 1-jump) a 2-jump lands on stone 3: dp[2][2] is now reachable.
  4. From stone 3 (reached on a 2-jump) a 2-jump lands on stone 5: dp[3][2] is now reachable.
  5. From stone 3 (reached on a 2-jump) a 3-jump lands on stone 6: dp[4][3] is now reachable.
  6. From stone 5 (reached on a 2-jump) a 1-jump lands on stone 6: dp[4][1] is now reachable.
  7. From stone 5 (reached on a 2-jump) a 3-jump lands on stone 8: dp[5][3] is now reachable.
  8. From stone 6 (reached on a 1-jump) a 2-jump lands on stone 8: dp[5][2] is now reachable.
  9. From stone 8 (reached on a 3-jump) a 4-jump lands on stone 12: dp[6][4] is now reachable.
  10. From stone 12 (reached on a 4-jump) a 5-jump lands on stone 17: dp[7][5] is now reachable. That is the last stone.
  11. dp[7] has 1 reachable jump size(s), so the frog CAN reach the last stone at 17.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Frog Jump in the editorAll Dynamic Programming problemsBack to roadmap