# Java Solution Using DP + HashMap

• ``````public boolean canCross(int[] stones) {
if (stones == null || stones.length == 0) {
return true;
}

HashMap<Integer, boolean[]> map = new HashMap<Integer, boolean[]>();
int last = stones[stones.length - 1];
if (last == Integer.MAX_VALUE) {
return false;
}
int maxStep = maxStep(last);
boolean[] cur = new boolean[maxStep + 1];
cur[0] = true;
map.put(0, cur);

for (int i = 1; i < stones.length; i++) {
int unit = stones[i];
cur = new boolean[maxStep + 1];  //whether I can jump j step to this unit
for (int j = 1; j < cur.length; j++) {
if (!map.containsKey(unit - j)) {
cur[j] = false;
} else {
boolean[] pre = map.get(unit - j);
cur[j] = pre[j - 1] || pre[j];
if (j < cur.length - 1) {
cur[j] = cur[j] || pre[j + 1];
}
}
}
map.put(unit, cur);
}

cur = map.get(last);
boolean res = cur[0];
for (int i = 1; i < cur.length; i++) {
res = res || cur[i];
}
return res;
}

private int maxStep(int last) {
int i = 1;
int sum = 0;

while (sum < last) {
sum += i;
i++;
}
return i - 1;
}``````

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