AC Java code using DP idea

  • 0

    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>());
            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>());
            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.