Java O(n^2) DP Solution


  • 0
    1. Use hashmap to store the index of stones
    2. convert jump distance into index of stones
    3. once reach the final index, then return true;

    Suppose current stone is i, can jump step is k
    then the DP thought is that:
    dp[ idx of (stones[i] + k-1)][k-1] = true;
    dp[ idx of (stones[i] + k)][k] = true;
    dp[ idx of (stones[i] + k+1)][k+1] = true;
    Once reach the idx of the last stone, then return true;

    public class Solution {
        public boolean canCross(int[] stones) {
            int n = stones.length;
            if(n <= 1)return true;
            Map<Integer,Integer> map = new HashMap<Integer, Integer>(n);
            for(int i = 0; i < n; i++){
                map.put(stones[i],i);
            }
            boolean[][] dp = new boolean[n+1][n+1];
            dp[0][0] = dp[0][1] = true;
            for(int i = 0; i < n; i++){
                for(int j = 1; j < n; j++){
                    if(dp[i][j]){
                        int n1 = stones[i] + j - 1;
                        if(i > 0 && map.containsKey(n1)){
                            int i1 = map.get(n1);
                            if(i1 == n - 1)return true;
                            dp[i1][j-1] = true;
                        }    
                        int n2 = stones[i] + j;
                        if(map.containsKey(n2)){
                            int i2 = map.get(n2);
                            if(i2 == n-1)return true;
                            dp[i2][j] = true;
                        }
                        int n3 = stones[i] + j + 1;
                        if(i > 0 &&  map.containsKey(n3)){
                            int i3 = map.get(n3);
                            if(i3 == n-1)return true;
                            dp[i3][j+1] = true;
                        }    
                    }
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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