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