[leetcode] 403. Frog Jump

mo0n1andin 發(fā)布于2019-08-14 16:52 / 2638人閱讀

摘要：還有一個(gè)石頭可能由之前的多個(gè)石頭到達(dá)，這又是可以?xún)?yōu)化的地方。當(dāng)前結(jié)果可由之前的結(jié)果得出，且有重復(fù)的搜索方法，就需要用。

[鏈接描述]leetcode 題目。

有點(diǎn)類(lèi)似于jump game，只不過(guò)這里對(duì)步數(shù)有了隱形的要求，當(dāng)前步數(shù)和之前步數(shù)有關(guān)。
如果我們用brute force的方法來(lái)解，每一步有三種可能，一共n個(gè)石頭，時(shí)間復(fù)雜度就是O(3^n)。
這其中有很多步數(shù)是多余的，第i個(gè)石頭無(wú)法從任何一個(gè)石頭到達(dá)，那么我們應(yīng)該立即中止搜尋。
還有一個(gè)石頭可能由之前的多個(gè)石頭到達(dá)，這又是可以?xún)?yōu)化的地方。
當(dāng)前結(jié)果可由之前的結(jié)果得出，且有重復(fù)的搜索方法，就需要用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 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 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 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;
    }
}