力扣-887-鸡蛋掉落

评论

题目：
887. Super Egg Drop(hard)

解题思路：
状态：
dp[K][N]:当前有K个鸡蛋，还有N层楼需要测式时最小移动的次数
选择：
当选择在第i层扔鸡蛋时：
当鸡蛋碎了：dp[K][N] = dp[K-1][i-1]
当鸡蛋没碎：dp[K][N] = dp[K][N-i]
base case:
dp[K][0] = 0:没有楼层需要测试，需要0次
dp[1][n] = 1:只有一个鸡蛋只能从低到高逐层试，需要n次

递归求解：
消除重叠子问题：memo备忘录
减少计算规模：二分思想

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Integer[][] memo = null;
public int superEggDrop(int K, int N) {
    memo = new Integer[K+1][N+1];
    return dp(K,N);
}

private int dp(int k,int n){
    if(k == 1)  return n;
    if(n<= 0)   return 0;
    if(memo[k][n] != null)  return memo[k][n];

    int res = Integer.MAX_VALUE;

    //二分 时间复杂度O(KNlogN)
    int low = 1,high = n;
    while(low <= high){
        int mid = low + (high - low)/2;
        int eggBreak = dp(k-1,mid-1);
        int eggUnBreak = dp(k,n-mid);
        if(eggBreak > eggUnBreak){//最坏条件下
            high = mid - 1;
            res = Math.min(res,eggBreak+1);//最坏条件下选最小的情况
        }else{
            low = mid + 1;
            res = Math.min(res,eggUnBreak+1);//最坏条件下选最小的情况
        }
    }
    memo[k][n] = res;
    return res;
}
//https://leetcode-cn.com/problems/super-egg-drop/solution/la-bu-la-duo-xiao-hong-mao-da-niu-ti-jie-dai-ma-ja/
//https://leetcode-cn.com/problems/super-egg-drop/solution/ji-ben-dong-tai-gui-hua-jie-fa-by-labuladong/

InstantCWeedStudent

个人简介。