# DP+hashmap

• dp hashmap
A[i][j] pos i can be reached by one j-unit's jump. hashmap stores the pos which can be reached.
step min can be stones[i]-stones[i-1], max can be min(stones[i],i)-1

``````    public boolean canCross(int[] stones) {
if (stones.length < 1) return true;
if (stones[1] != 1) return false;
if (stones.length == 2) return true
boolean[][] dp = new boolean[stones.length][stones.length];
Map<Integer, Integer> map = new HashMap<>();
dp[1][1] = true;
map.put(stones[1], 1);
boolean flag = false;
for (int i = 2; i < stones.length; i++) {
for (int step = stones[i]-stones[i-1]; step < Math.min(stones[i], i+1); step++) {
Integer pos = map.get(stones[i]-step);
if (pos != null) {
for (int k = -1; k <= 1; k++) {
if (step+k > 0 && step+k < stones.length && dp[pos][step+k]) {
dp[i][step] = true;
flag = true;
if (i == stones.length-1) return true;
break;
}
}
}
}
if (flag) {
map.put(stones[i], i); flag = false;
}
}

return false;
}``````

• I think the fast solution for this problem is memory dfs. As we only want a valid solution is ok, but dp solution needs to traverse all possible case.

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