AC Java code using DP idea


  • 0
    T

    An idea of DP. Each stone should have a set to record the num of steps the frog takes to reach this stone. There could be many possibilities and all these steps could be used later.

    public class Solution {
        public boolean canCross(int[] stones) {
            if (stones.length == 0) return false;
            if (stones.length == 1) return true;
            
            Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
            map.put(0, new HashSet<Integer>());
            map.get(0).add(0);
            
            for (int i = 0; i < stones.length; i++){
                if (!map.containsKey(i)) continue;
                
                Set<Integer> JumpOptions = map.get(i);
                for (int step: JumpOptions){
                
                    for (int j = i+1; j < stones.length; j++){
                        int loc = stones[i] + step;
                        if (loc + 1 < stones[j]) break;
                        for (int z = -1; z < 2; z++){
                            if (loc + z == stones[j]){
                                if (!map.containsKey(j)) map.put(j, new HashSet<Integer>());
                                map.get(j).add(step+z);
                            }
                        }
                    }
                }
            }
            
            return map.containsKey(stones.length-1);
            
        }
    }
    

Log in to reply
 

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