经典动态规划：高楼扔鸡蛋 :: labuladong的算法小抄

[labuladong]

文章链接点这里：经典动态规划：高楼扔鸡蛋

评论礼仪 见这里，违者直接拉黑。

[sonymoon]

递归+备忘录 lc上超时了

[1302304703]

备忘录+递归确实会超时
在第74个用例的时候,输入数据是: s = 6 , n = 10000

class Solution {
    int[][] memo;

    public int superEggDrop(int k, int n) {
        memo = new int[k + 1][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -999);
        }
        return dp(k, n);
    }

    //k个鸡蛋,n层楼,返回最优结果
    public int dp(int k, int n) {
        //base case
        if (k == 1) {
            return n;
        }
        if (n == 0) {
            return 0;
        }

        //备忘录
        if (memo[k][n] != -999) {
            return memo[k][n];
        }

        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            res = Math.min(res, Math.max(dp(k - 1, i - 1),
                    dp(k, n - i)) + 1);
        }

        memo[k][n] = res;
        return res;
    }
}

[tiandee]

得用二分搜索进行优化，不然lt提交会超时

[yihang-gao]

其实就算二分搜索，python会超时...。看了几个YouTube博主，py也超了，，，

[cheng-miao]

1

[Maxiah]

会超时，但是想往之前的套路里塞一塞

class Solution {
public:
    vector<vector<int>> memo;   // 备忘录
    int superEggDrop(int k, int n) {
        // 自底向上的DP

        // 状态：鸡蛋，楼层
        // 选择：碎没碎
        memo = vector<vector<int>>(k+1, vector<int>(n+1));

        // dp[i][j]表示：当前手握i个鸡蛋身处j层楼的最少扔鸡蛋次数是dp[k][j]。
        vector<vector<int>> dp(k+1, vector<int>(n+1));

        // base case
        for(int i = 1; i < dp.size(); i++){
            for(int j = 1; j < dp[0].size(); j++){
                dp[i][j] = j;
            }
        }
        

        // 穷举所有状态
        // int res = INT_MAX;
        for(int i = 2; i < dp.size(); i++){ // 鸡蛋
            for(int j = 1; j < dp[0].size(); j++){  // 楼层
                // 穷举选择：在第几层楼扔
                // 碎了，去楼下
                // 没碎，去楼上

                for(int h = 1; h <= j; h++){
                    dp[i][j] = min(dp[i][j],
                                   max(dp[i - 1][h - 1], dp[i][j-h]) + 1);
                }
            }
        }

        return dp[k][n];
    }
};

[tiandee]

对套路很重要

[lauloong]

第二种dp定义+空间压缩

class Solution {
    public int superEggDrop(int k, int n) {
        // dp[i][j] 有i个鸡蛋，最多扔j次时，最坏情况下最多能测的最大楼层数
        
        int[] dp = new int[k + 1];
        int m = 0;
        while(dp[k] < n) {
            m++;
            int pre = 0;
            for(int i = 1; i <= k; i++) {
                int tmp = dp[i];
                // 最多m次的能测的楼层数 = 该层没碎 + 该层碎了 + 该层
                dp[i] = dp[i] + pre + 1;
                pre = tmp;
            }
        }
        return m;
    }
}

[yihang-gao]

请问为什么是该层没碎 + 该层碎了 啊

[Trae1ounG]

你好，为啥我分析感觉最后的O(K*logN)的算法不可行呢？

int lo = 1,hi = n;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (... < N){
        // ①
    }else{
        //②
    }
    for i in k {
         .... 
    }
}

首先，①、②处一定是利用的dp[k][mid]来判断，此时使用的为dp数组，自底向上的而非自顶向下，并不能往下递归得出值。
此时的dp[k][mid]还未赋上值，无法作为判断条件。

[GoingMyWay]

这个题目的一个很大的疑惑是：怎么判断鸡蛋碎没碎？题目没有任何提示。

[GoingMyWay]

再次看了题目，我发现题目的结构这个类似于博弈树的结构。每一次选择都有碎或者不碎的结果。所以碎没碎不是关键。

[laoyoutiao237]

我现在不仅想知道最小操作数，还想知道它具体是怎么选择楼层进行试探的，该怎么写代码？

[CarlLy7]

个人感觉 最坏情况就是楼层尽可能高， 最少次数就是用尝试次数最少来确定尽可能高的恰好不摔坏的楼层

[CarlLy7]

打卡，附上详细注解的Java代码

    //下面写一下使用二分搜索优化的自顶向下的动态规划算法。
    //使用动态规划必须先明确状态和选择 状态：可以尝试的鸡蛋次数，楼层数  选择：从哪个楼层扔鸡蛋
    //因为是一个自顶向下的动态规划问题，这个问题中有重叠子问题，所以使用备忘录来消除重叠子问题
    int[][] memo;

    public int superEggDrop(int k, int n) {
        //整体右移一位，从下标1开始更符合生活实际
        memo = new int[k + 1][n + 1];
        for (int[] ints : memo) {
            Arrays.fill(ints, -1);
        }
        return dp(k, n);
    }

    //声明一下dp函数的定义：当有k个鸡蛋，n层楼的时候确定恰好不碎的楼层的最少尝试次数为dp(k,n)
    private int dp(int k, int n) {
        //base case
        //1.当我们只有一个鸡蛋的时候，只能进行线性扫描才能确定最坏情况下的恰好不碎的楼层
        if (k == 1) {
            return n;
        }
        //2.当楼层为0或者鸡蛋为0的时候，尝试的次数肯定为0
        if (k == 0 || n == 0) {
            return 0;
        }
        if(memo[k][n]!=-1){
            return memo[k][n];
        }
        //状态转移方程：如果此时碎了，那么楼层在当前楼层的下面，楼层数为i-1 如果没有随楼层在当前楼层上面，楼层数为n-i
        // 因为是最坏情况下所以碎没碎取决于尝试的次数，选择尝试次数多的那个
        int res = Integer.MAX_VALUE;
        int low = 1, high = n;
        while (low <= high) {
            //这个mid其实就是使用二分搜索快速知道的中间的尝试楼层，也就是当前仍的那个楼层
            int mid = (low + high) / 2;
            //鸡蛋碎的情况
            int broke = dp(k - 1, mid - 1);
            //鸡蛋没有碎的情况
            int not_broke = dp(k, n - mid);
            //因为是最坏情况下，所以我们选择碎或者没碎中尝试次数最多，也就是最大的那个
            if (broke > not_broke) {
                //碎的情况下尝试的次数多于不碎
                //下次我们应该去楼下尝试
                high = mid - 1;
                //因为最后结果是尝试次数最少，所以取最小值
                res = Math.min(res, broke + 1);
            } else {
                //不碎的情况下尝试的次数多于碎
                //下次我们应该去楼上尝试
                low = mid + 1;
                res = Math.min(res, not_broke + 1);
            }
        }
        memo[k][n] = res;
        return res;
    }

[CarlLy7]

解法2

    //下面换一个dp定义的思路

    public int superEggDrop(int K, int n) {
        //dp数组的定义:dp[k][m]表示有k个鸡蛋，最少尝试m次可以确定的最高的楼层是dp[k][m]
        //这里为什么大小设置为[n+1]呢。因为确定楼层N层需要的最少的次数最多也就是n次
        int[][] dp = new int[K + 1][n + 1];
        //base case
        //1.当鸡蛋为0的时候，确定的高度为0
        for (int m = 0; m < n + 1; m++) {
            dp[0][m] = 0;
        }
        //2.当尝试次数m为0的时候可以确定的楼层也为0
        for (int i = 0; i < K - 1; i++) {
            dp[i][0] = 0;
        }
        //当我们可以确定的楼层高度达到了n层，那么就结束了
        int m = 0;
        while (dp[K][m] < n) {
            m++;//尝试的次数+1
            for (int k = 1; k <= K; k++) {
                //当前可以确定的最高高度=楼下的高度+楼上的高度+1
                //dp[k][m-1]代表没碎，所以确定楼下的高度
                //dp[k-1][m-1]代表碎了，确定楼上的高度
                //加1是当前的楼层
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
            }
        }
        return m;
    }

[tiandee]

秀儿，你真棒

[RayL01]

为什么每次要在碎于不碎之前取最大值呢，这个不是很理解