高楼扔鸡蛋-memorization search

[TOC]

题解:

LeetCode 887. Super Egg Drop.

这是一道经典的谷歌面试题，某公司今天的笔试题出了这道题（只不过扔的不是鸡蛋）。

理解题意

这道题是总共有N层楼，K个鸡蛋，找到鸡蛋摔破的极限楼层。最小需要尝试多少次，

(表示我第一次看到这道题，以为是一道数学题，并且还想眼巴巴的算出来。)

考虑状态转移，很容易想到动态规划。

假设从h楼摔下，如果摔碎，则状态变为：（K-1, h-1) （即K-1个鸡蛋，总共有h-1楼）

如果没摔碎，则状态变为：（K, N-h)

由此很容易写出递推式：

$$dp[k][n] = min(1+max(dp[k-1][i-1], dp[k][n-i])) \ i=1…n $$

由递推式得到代码：

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K+1][N+1];
        for (int i = 1; i < K+1; i++) {
            for (int j = 1; j < N+1; j++) {
                dp[i][j] = j;
            }
        }
        for (int i = 2; i < K+1; i++) {
            for (int j = 1; j < N+1; j++) {
                for (int j2 = 1; j2 < j; j2++) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][j2-1], dp[i][j-j2])+1);   
                }
            }
        }
        return dp[K][N];
    }
}

递归版：

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] memo = new int[K + 1][N + 1];
        return dfs(K, N, memo);
    }
    public int dfs(int K, int N, int[][] memo){
        // base case
        if(N<=1 || K==1){
            return N;
        }
        // memorization
        if(memo[K][N]>0) 
            return memo[K][N];
        int min = N;
        for (int i = 1; i < N; i++) {
            int left = dfs(K-1, i-1, memo);
            int right = dfs(K, N-i, memo);
            min = Math.min(min, Math.max(left, right)+1); 
        }
        memo[K][N] = min;
        return min;
    }
}

这样会超时，优化！从迭代版的代码可以看出，时间复杂度为 $O(KN^2)$,其中搜索$dp[k][n] = min(1+max(dp[k-1][i-1], dp[k][n-i])) \ i=1…n $中的i可以用二分搜索。从而将时间复杂度将为$O(KNlogN)$.

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K+1][N+1];
        for (int i = 1; i < K+1; i++) {
            for (int j = 1; j < N+1; j++) {
                dp[i][j] = j;
            }
        }
        for (int i = 2; i < K+1; i++) {
            for (int j = 1; j < N+1; j++) {
                int lo =1, hi  = j;
                int min = dp[i][j];
                while(lo<hi){
                    int mid = lo+(hi-lo)/2;
                    int left = dp[i-1][mid-1];
                    int right = dp[i][j-mid];
                    min = Math.min(min, Math.max(left, right)+1);
                    if(left == right)
                        break;
                    else if(left < right)
                        lo = mid+1;
                    else
                        hi = mid;
                }
                dp[i][j] = min;
            }
        }
        return dp[K][N];
    }
}

递归版：

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] memo = new int[K + 1][N + 1];
        return dfs(K, N, memo);
    }
    public int dfs(int K, int N, int[][] memo){
        // base case
        if(N<=1 || K==1){
            return N;
        }
        // memorization
        if(memo[K][N]>0) 
            return memo[K][N];
        int lo=1, hi =N, res = N;
        while(lo<hi){
            int mid = lo + (hi-lo)/2 ;
            int left = dfs(K-1, mid-1, memo);
            int right = dfs(K, N-mid, memo);
            res = Math.min(res, Math.max(left, right)+1);
            if(left==right){
                break;
            }else if(left<right){
                lo = mid+1;
            }else{
                hi=mid;
            }
        }
        memo[K][N] = res;
        return res;
    }
}