# easy DP solution (java), can anyone improve it. Some testcases seem wrong

• map<Integer, set<Integer>>: used to record (stone pos, ith stone's all valid lastUnits to next stone)
DP - solution: time O(n^2), space O(n)

Rationale is: for the ith stone, check if frog can jump from any previous stone to the ith stone. use map to record the "i - [lastUnits]" pair.

Can anyone improve this DP solution? The time to pass Leetcode test cases is 408s. Still too long time

Another question about the test case:
Why should [0], [0,0], [2,2] return true? Based on problem description, the stones.length must >= 2 and stones[1] - stones [ 0] should == 1. Because landed on 0th stone, frog must jump 1 unit to 1st stone. [0,0] should return false.

``````public class Solution {
public boolean canCross(int[] stones) {
if (stones == null || stones.length <= 0) {
return false;
}
if (stones.length == 1) {
return true;
}
if (stones[1] - stones[0] != 1) {//1st jump must be 1 unit
return false;
}
Map<Integer, Set<Integer>> map = new HashMap<>();
map.put(1, new HashSet<Integer>());

for (int i = 2; i < stones.length; i++) {
for (int j = i - 1; j >= 1; j--) {
if (!map.containsKey(j)) {
continue;
}
if (!canJump(map.get(j), stones[i] - stones[j])) {
continue;
}
if (!map.containsKey(i)) { //can jump from jth to ith stone, record it
map.put(i, new HashSet<Integer>());
}
}
}
return !map.containsKey(stones.length - 1) ? false : true;
}
//check if can jump from jth stone to the ith stone
private boolean canJump(Set<Integer> lastUnits, int target) {
if (lastUnits.contains(target) || lastUnits.contains(target - 1) || lastUnits.contains(target + 1)) {
return true;
}
return false;
}
}
``````

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