# Java O(n^2) DP Solution

1. Use hashmap to store the index of stones
2. convert jump distance into index of stones
3. once reach the final index, then return true;

Suppose current stone is i, can jump step is k
then the DP thought is that:
dp[ idx of (stones[i] + k-1)][k-1] = true;
dp[ idx of (stones[i] + k)][k] = true;
dp[ idx of (stones[i] + k+1)][k+1] = true;
Once reach the idx of the last stone, then return true;

``````public class Solution {
public boolean canCross(int[] stones) {
int n = stones.length;
if(n <= 1)return true;
Map<Integer,Integer> map = new HashMap<Integer, Integer>(n);
for(int i = 0; i < n; i++){
map.put(stones[i],i);
}
boolean[][] dp = new boolean[n+1][n+1];
dp[0][0] = dp[0][1] = true;
for(int i = 0; i < n; i++){
for(int j = 1; j < n; j++){
if(dp[i][j]){
int n1 = stones[i] + j - 1;
if(i > 0 && map.containsKey(n1)){
int i1 = map.get(n1);
if(i1 == n - 1)return true;
dp[i1][j-1] = true;
}
int n2 = stones[i] + j;
if(map.containsKey(n2)){
int i2 = map.get(n2);
if(i2 == n-1)return true;
dp[i2][j] = true;
}
int n3 = stones[i] + j + 1;
if(i > 0 &&  map.containsKey(n3)){
int i3 = map.get(n3);
if(i3 == n-1)return true;
dp[i3][j+1] = true;
}
}
}
}
return false;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.