DP+hashmap


  • 0
    F

    dp hashmap
    A[i][j] pos i can be reached by one j-unit's jump. hashmap stores the pos which can be reached.
    step min can be stones[i]-stones[i-1], max can be min(stones[i],i)-1

        public boolean canCross(int[] stones) {
           if (stones.length < 1) return true;
            if (stones[1] != 1) return false;
            if (stones.length == 2) return true        
            boolean[][] dp = new boolean[stones.length][stones.length];
            Map<Integer, Integer> map = new HashMap<>();
            dp[1][1] = true;
            map.put(stones[1], 1);
            boolean flag = false;
            for (int i = 2; i < stones.length; i++) {
                for (int step = stones[i]-stones[i-1]; step < Math.min(stones[i], i+1); step++) {
                    Integer pos = map.get(stones[i]-step);
                    if (pos != null) {
                        for (int k = -1; k <= 1; k++) {
                            if (step+k > 0 && step+k < stones.length && dp[pos][step+k]) {
                                dp[i][step] = true; 
                                flag = true;
                                if (i == stones.length-1) return true; 
                                break;
                            }
                        }
                    }
                }
                if (flag) {
                    map.put(stones[i], i); flag = false;
                }
            }
            
            return false;
        }

  • 0
    F

    I think the fast solution for this problem is memory dfs. As we only want a valid solution is ok, but dp solution needs to traverse all possible case.


Log in to reply
 

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