# 403. Frog Jump

• Time: $O(n^2)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: bool canCross(vector& stones) { const int n = stones.size(); // dp[i][j] := true if a frog can make a size j jump to stones[i] vector> dp(n, vector(n + 1)); dp[0][0] = true; for (int i = 1; i < n; ++i) for (int j = 0; j < i; ++j) { const int k = stones[i] - stones[j]; if (k > n) continue; for (const int x : {k - 1, k, k + 1}) if (0 <= x && x <= n) dp[i][k] = dp[i][k] || dp[j][x]; } return any_of(begin(dp.back()), end(dp.back()), [](bool val) { return val; }); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public boolean canCross(int[] stones) { final int n = stones.length; // dp[i][j] := 1 if a frog can make a size j jump to stones[i] int[][] dp = new int[n][n + 1]; dp[0][0] = 1; for (int i = 1; i < n; ++i) for (int j = 0; j < i; ++j) { final int k = stones[i] - stones[j]; if (k > n) continue; for (final int x : new int[] {k - 1, k, k + 1}) if (0 <= x && x <= n) dp[i][k] |= dp[j][x]; } return Arrays.stream(dp[n - 1]).anyMatch(a -> a == 1); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def canCross(self, stones: List[int]) -> bool: n = len(stones) # dp[i][j] := True if a frog can make a size j jump to stones[i] dp = [[False] * (n + 1) for _ in range(n)] dp[0][0] = True for i in range(1, n): for j in range(i): k = stones[i] - stones[j] if k > n: continue for x in (k - 1, k, k + 1): if 0 <= x <= n: dp[i][k] |= dp[j][x] return any(dp[-1]) 

## Approach 2: Jump from

• Time: $O(n^2)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: bool canCross(vector& stones) { const int n = stones.size(); // dp[i][j] := true if a frog can make a size j jump from stones[i] vector> dp(n, vector(n + 1)); dp[0][1] = true; for (int i = 1; i < n; ++i) for (int j = 0; j < i; ++j) { const int k = stones[i] - stones[j]; if (k <= n && dp[j][k]) { dp[i][k - 1] = true; dp[i][k] = true; dp[i][k + 1] = true; } } return any_of(begin(dp.back()), end(dp.back()), [](bool val) { return val; }); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public boolean canCross(int[] stones) { final int n = stones.length; // dp[i][j] := 1 if a frog can make a size j jump from stones[i] int[][] dp = new int[n][n + 1]; dp[0][1] = 1; for (int i = 1; i < n; ++i) for (int j = 0; j < i; ++j) { final int k = stones[i] - stones[j]; if (k <= n && dp[j][k] == 1) { dp[i][k - 1] = 1; dp[i][k] = 1; dp[i][k + 1] = 1; } } return Arrays.stream(dp[n - 1]).anyMatch(a -> a == 1); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def canCross(self, stones: List[int]) -> bool: n = len(stones) # dp[i][j] := True if a frog can make a size j jump from stones[i] dp = [[False] * (n + 1) for _ in range(n)] dp[0][1] = True for i in range(1, n): for j in range(i): k = stones[i] - stones[j] if k <= n and dp[j][k]: dp[i][k - 1] = True dp[i][k] = True dp[i][k + 1] = True return any(dp[-1])