403.Frog Jump

1-DFS

class Solution {
    public boolean canCross(int[] stones) {
        int dest = stones[stones.length - 1];
        int cur = 0;
        Map<String, Boolean> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for(int i : stones){
            set.add(i);
        }
        return helper(set, map, 0, dest, 1);
    }
    public boolean helper(Set<Integer> stones, Map<String, Boolean> map, int cur, int dest, int speed){
        String key = cur + "#" + speed;
        if(map.containsKey(key))
            return map.get(key);

        if(cur == dest){
            map.put(key, true);
            return true;
        }
        else{
            int nextPos = cur + speed;
            if(!stones.contains(nextPos)){
                map.put(key, false);
                return false;
            }
            if(nextPos > dest){
                map.put(key, false);
                return false;
            }
            else{
                boolean res1 = false;
                if(speed > 1){
                    res1 = helper(stones, map, nextPos, dest, speed - 1);
                }
                boolean res2 = helper(stones, map, nextPos, dest, speed);
                boolean res3 = helper(stones, map, nextPos, dest, speed + 1);
                boolean res = res1 || res2 || res3;
                map.put(key, res);
                return res;
            }
        }
    }
}

2-DP

https://leetcode.com/problems/frog-jump/solution/

class Solution {
    public boolean canCross(int[] stones) {
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        for(int i = 0; i < stones.length; i++){
            map.put(stones[i], new HashSet<>());
        }
        map.get(0).add(0);
        for(int i = 0; i < stones.length; i++){
            for(int k : map.get(stones[i])){
                for(int step = k - 1; step <= k + 1; step++){
                    if(step > 0 && map.containsKey(stones[i] + step)){
                        map.get(stones[i] + step).add(step);
                    }
                }
            }
        }
        return map.get(stones[stones.length - 1]).size() > 0;
    }
}