# Java DP solution O(n^2) and Recursion using memorization

• For the DP code, the time cost is high. It just fairly past the tests. The time complexity is O(n^2). Not clear why it takes so long

``````    //DP
public boolean canCross(int[] stones) {
if (stones.length == 2) return stones[1] == 1;
//Map[stone]:all possible previous steps to reach this stone
Set<Integer>[] myMap = new HashSet[stones.length];

//first stone
myMap[0] = new HashSet<Integer>();
//first can be reach with last step size 1

for (int i = 1; i < stones.length; i++) {
for (int j = i - 1; j >= 0; j--) {
//if stone j can not be reached
if (myMap[j] == null)continue;

//Since the stone is sorted, if last steps needed to reach stone i is larger than the maximum
//possible steps needed to reach j, break.
int step = stones[i] - stones[j];
if (step > stones[j] + 1) break;

//if the stone i can be reached from stone j, uppdate stone i
if (myMap[j].contains(step) || myMap[j].contains(step - 1) ||
myMap[j].contains(step + 1)) {
if (myMap[i] == null) myMap[i] = new HashSet<Integer>();
}

}

}

return myMap[stones.length - 1] != null;
}
``````

Recursion: Time lime exceed. Do not know why....It seems I used similar idea as others....

`````` Recursion with memory

public boolean canCross(int[] stones) {
Set<Integer>[] myMap = new HashSet[stones.length];

return helper(myMap, stones, 0, 0);

}

public boolean helper(Set<Integer>[] myMap, int[] stones, int start, int preStep) {
if (myMap[start] != null && myMap[start].contains(preStep)) return true;

for (int next = start + 1; next < stones.length; next++) {
int gap = stones[next] - stones[start];
if (gap < preStep - 1) continue;
if (gap > preStep + 1) return false;
if (helper(myMap, stones, next, gap)) {
if (myMap[start] == null) myMap[start] = new HashSet<Integer>();
return true;
}
}

if (start == stones.length - 1) {
if (myMap[start] == null) myMap[start] = new HashSet<Integer>();