• Time:O(n^2)
• Space:O(n^2)

## C++

``````class Solution {
public:
bool canCross(vector<int>& stones) {
const int n = stones.size();
// dp[i][j] := true if a frog can make a size j jump to stones[i]
vector<vector<bool>> dp(n, vector<bool>(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; });
}
};
``````

## JAVA

``````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);
}
}
``````

## Python

``````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])
``````

• Time:O(n^2)
• Space:O(n^2)

## C++

``````class Solution {
public:
bool canCross(vector<int>& stones) {
const int n = stones.size();
// dp[i][j] := true if a frog can make a size j jump from stones[i]
vector<vector<bool>> dp(n, vector<bool>(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; });
}
};
``````

## JAVA

``````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);
}
}
``````

## Python

``````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])
``````