# Java 24ms recrusive solution

• basic idea is to use a boolean matrix to save intermediate result. initially used 2-D array, but seems hashmap perform better.

dp[i] is a hash map, which stores if it's possible to reach from stone 0 to i with possible final steps. so it dp[i].get(k) == true means it's possible to reach stone i and the final step jumps k units.

``````  public boolean canCross(int[] stones) {
int n = stones.length;
if (n <= 1) return true;
if (n == 2) return stones[1] == 1;
Map<Integer, Integer> indexs = new HashMap<>();
for (int i = 0; i < n; i++) indexs.put(stones[i], i);
HashMap<Integer, Boolean>[] dp = new HashMap[n];
dp[0] = new HashMap<>();
dp[0].put(0, true);
dp[1] = new HashMap<>();
dp[1].put(1, true);
for (int i = n - 1 ; i >= 0; i--) {
if (canReach(stones, indexs, n - 1, stones[n - 1] - stones[i], dp)) return true;
}
return false;
}

private boolean canReach(int[] stones, Map<Integer, Integer> indexs, int end, int steps, HashMap<Integer, Boolean>[] dp) {
dp[end] = (dp[end] == null ? new HashMap<>() : dp[end]);
Boolean result = dp[end].get(steps);
if (result == null) {
Integer index = indexs.get(stones[end] - steps);
result = false;
if (index != null) {
for (int i = -1; i <= 1; i++) {
if ((steps + i) > 0 && canReach(stones, indexs, index, steps + i, dp)) {
result = true;
break;
}
}
}
dp[end].put(steps, result);
}
return result;
}
``````

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