Java DP solution with memoization


  • 0
    A
        public boolean canCross(int[] stones) {
    
            Set<Integer> preparedStones = new HashSet<Integer>(stones.length);
            for (int step : stones) {
                preparedStones.add(step);
            }
            Map<String, Boolean> cache = new HashMap<String, Boolean>();
            return canCross(preparedStones, 0, 1, cache, stones[stones.length - 1]);
    
        }
    
        private boolean canCross(Set<Integer> steps, int lastStep, int k, Map<String, Boolean> cache, int lastStone) {
    
            String mapKey = lastStep + "," + k;
    
            if (cache.get(mapKey) != null) return cache.get(mapKey);
            if (k <= 0 || !steps.contains(lastStep)) return false;
            if (lastStep == lastStone) return true;
    
            boolean result = canCross(steps, lastStep + k, k, cache, lastStone)
                    || canCross(steps, lastStep + k, k - 1, cache, lastStone)
                    || canCross(steps, lastStep + k, k + 1, cache, lastStone);
    
            cache.put(mapKey, result);
            return cache.get(mapKey);
        }
    ```

Log in to reply
 

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