[leetcode] 403. Frog Jump

NO IMAGE

[連結描述]leetcode 題目。


有點類似於jump game, 只不過這裡對步數有了隱形的要求,當前步數和之前步數有關。
如果我們用brute force的方法來解,每一步有三種可能,一共n個石頭,時間複雜度就是O(3^n)。
這其中有很多步數是多餘的,第i個石頭無法從任何一個石頭到達,那麼我們應該立即中止搜尋。
還有一個石頭可能由之前的多個石頭到達,這又是可以優化的地方。
當前結果可由之前的結果得出,且有重複的搜尋方法,就需要用DP。

public class Solution {
    public boolean canCross(int[] stones) {
        if(stones[1] != 1) return false;
        int n = stones.length;
        int[][] dp = new int[n][n];     // for ith stones, j means maximun previous steps
        for(int i=0; i<n;i  ){
            for(int j=0; j<n;j  ){
                dp[i][j] = -1;
            }
        }
        return canCross(dp, stones, 0, 0, n);
    }
    
    public boolean canCross(int[][] dp, int[] stones, int i, int j, int n){
        if(dp[i][j] != -1) return dp[i][j] == 1;
        if(i == n-1){
            dp[i][j] = 1; 
            return true;
        }
        
        for(int k=i 1; k < n; k  ){
            if(stones[k] < stones[i]   j - 1){      // too close
                continue;
            } else if(stones[k] > stones[i]   j   1){    // too far
                dp[i][j] = 0;
                continue;
            } else {   // j-1, j, j 1 three possibility 
                if(canCross(dp, stones, k, stones[k] - stones[i], n)){
                    dp[i][j] = 1;
                    return true;
                }
            }
        }
        
        dp[i][j] = 0;
        return false;
    }
}

public class Solution {
    public boolean canCross(int[] stones) {
        if(stones == null || stones.length == 0) return false;
        int n = stones.length;
        if(n == 1)  return true;
        if(stones[1] != 1) return false;
        if(n == 2)  return true;
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i  ){
            if(i > 3 && stones[i] > stones[i-1]*2) return false;
            set.add(stones[i]);
        }
        
        return canCross(set, stones[n-1], 1, 1);
    }
    
    public boolean canCross(HashSet<Integer> set, int last, int pos, int jump){
        if(pos   jump == last || pos   jump   1 == last || pos   jump -1 == last){
            return true;
        }
        if(set.contains(pos   jump   1)){
            if(canCross(set, last, pos jump 1, jump 1)) return true;
        }
        if(set.contains(pos   jump)){
            if(canCross(set, last, pos jump, jump)) return true;
        }
        if(jump > 1 && set.contains(pos   jump-1)){
            if(canCross(set, last, pos jump-1, jump-1)) return true;
        }
        return false;
    }
}