# Java DFS with memorization and some math for early termination (19ms)

• Similar idea with other DFS solution by going from the first one to the last.
From the observation, I found that there are lower bound and upper bound from stone 1 to stone n of n steps. The minimum steps is Max(n, k-1) and the maximum steps is (k+1)+(k+2)+(k+3)+....+(k+n).
Therefore, if the value of last stone is less than minimum steps or greater than maximum steps, we know that there is no way to reach it from current stone.
For example, with the case of `[0,1,3,6,10,11, 100]`
when `from = 0`, `to = 6` which has `stones[0] = 0`, `stones[6]=100`, and `k=1`
also, `len = 6-0=6`.
Therefore, the maximum steps from 0 to 6 with `k = 1` is `1+2+3+4+5+6 = 21` and
maximum stone value is `0+21=21`. Since `stones[6]=100`, it is impossible to jump from stone 0 to stone 6 when k=1.
On the other hand, when `from = 4`, `to = 5` which has `stones[4] = 10`, `stones[5]=11`, and `k=4`, also, `len = 5-4=1`.
Therefore, the minimum steps from 4 to 5 with `k = 4` is `Max(1,4-1) = 3` and
minimum stone value is `10+3=13`. Since `stones[5]=11`, it is impossible to jump from stone 4 to stone 5 when k=4.

``````public class Solution {
Map<Integer, Integer> map = new HashMap<>();
Set<String> mem = new HashSet<>();
int to;
int goal;
boolean dfs(int from, int k, int[] stones){
if (from == to) return true;
int cur = stones[from];
int len = to-from;
String key = ""+from +":"+k;
if ( mem.contains(key) ) return false;
if ( (goal > cur + ( (k+1+k+len)*len )/2) || (goal < cur + Math.max(len, k-1)) ) {
mem.add(key);
return false;
}
for (int next=k+1; next >=k-1; next--) {
if ( (next >= 1) && map.containsKey(cur+next) ) {
if ( dfs( map.get(cur+next), next, stones) ) return true;
}
}
mem.add(key);
return false;
}
public boolean canCross(int[] stones) {
if (stones == null || stones.length <=1) return true;
to = stones.length-1;
goal = stones[to];
for (int i=1; i <= to; i++) {
map.put(stones[i], i);
}
return dfs( 0, 0, stones);
}
}
``````

• Another DFS version incorporating the math to find the range. (18ms)

``````public class Solution {
Set<String> mem = new HashSet<>();
int to;
int goal;
boolean dfs(int from, int k, int[] stones){
int cur = stones[from];
int len = to-from;
String key = ""+from +":"+k;
if ( mem.contains(key) ) return false;
if ( goal >= cur+k-1 && goal <= cur+k+1) return true;
int min = cur + Math.max(len, k);
int max = cur + ( (k+1+k+len)*len )/2;
if (len > 1 && goal <= max && goal >= min ) {
for (int i=from+1; i<=to-1; i++) {
int next = stones[i]-cur;
if ( next >= k-1 && next <= k+1) {
if ( dfs( i, next, stones) ) {
return true;
}
}
}
}
mem.add(key);
return false;
}
public boolean canCross(int[] stones) {
if (stones == null || stones.length <=1) return true;
to = stones.length-1;
goal = stones[to];
return dfs( 0, 0, stones);
}
}
``````

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