Leetcode-887-鸡蛋掉落

Leecode-Super Egg Drop

思路：动态规划+二分搜索

题目描述

建议直接看李永乐老师视频理解题意：

https://www.bilibili.com/video/BV1KE41137PK?from=search&seid=17973611971894816621

下面是文字版描述

题目中「移动」的意思是：做一次实验，把一个鸡蛋从某个楼层扔下去，看它是否破碎。没有破碎的鸡蛋可以重复使用；

这 K 个鸡蛋，F 值满足的特点是：

• 在所有小于等于 F 的楼层扔下它不破碎；

• 在所有大于 F 的楼层扔下它一定会破碎

• F值是确定的，并且 0 <= F <= N，即 F 值一定不会超过楼层高度。

题目最根本要求解的问题：

• 找到这个 F 值的最小实验次数

• 时间复杂度是在最坏情况下（即运气最差的情况下），程序执行完毕最少执行的次数，

• 简而言之：用最好的算法，即使是在最坏的运气下，为了准确得到结果，找到 F 这个值的实验的次数最少是多少。

动态规划

• 显然这种最优化的问题，只问结果，不问过程，就是用【动态规划】去求解。

• 动态规划，可以认为是一种打表格的方法（定义来自《算法导论》）。

• 如果没有学习「动态规划」，我们还有「递归」，然后发现重复子问题，使用「缓存」记住结果是非常自然的，这叫「记忆化递归」（或者「记忆化搜索」）。

• 但是动态规划给我们另一种思路，可以从一个问题最初的样子去考虑它是如何一步一步得到最终的结果。

「动态规划」的两个思考方向：

• 自顶向下求解，称之为「记忆化递归」：初学的时候，建议先写「记忆化递归」的代码，然后把代码改成「自底向上」的「递推」求解；
• 自底向上求解，称之为「递推」或者就叫「动态规划」：在基础的「动态规划」问题里，绝大多数都可以从这个角度入手，做多了以后建议先从这个角度先思考，实在难以解决再考虑「记忆化递归」。

详细题解

第 1 步：定义状态

dp[i] [j]：一共有 i 层楼梯（注意：这里 i 不表示高度）的情况下，使用 j 个鸡蛋的最少实验的次数。

说明：

• i 表示的是楼层的大小，不是高度（第几层）的意思，例如楼层区间 [8, 9, 10] 的大小为 3。
• j 表示可以使用的鸡蛋的个数，它是约束条件。
  第一个维度最先容易想到的是表示楼层的高度，这个定义的调整是在状态转移的过程中完成的。因为如果通过实验知道了鸡蛋的 F 值在高度区间 [8, 9, 10] 里，这个时候只有 1 枚鸡蛋，显然需要做 3 次实验，和区间的大小是相关的。

第2步：推导转移方程

推导状态转移方程经常做的事情是「分类讨论」

这里「分类讨论」的依据就是，在指定的层数里扔下鸡蛋，根据这个鸡蛋是否破碎，就把问题拆分成了两个子问题。

• 如果鸡蛋破碎，测试 F 值的实验就得在 k 层以下做（不包括 k 层），这里已经使用了一个鸡蛋，因此测出 F 值的最少实验次数是：dp[k - 1] [j - 1]；
• 如果鸡蛋完好，测试 F 值的实验就得在 k 层以上做（不包括 k 层），这里这个鸡蛋还能使用，因此测出 F 值的最少实验次数是：dp[i - k] [j]，例如总共 8 层，在第 5 层扔下去没有破碎，则需要在 [6, 7, 8] 层继续做实验，因此区间的大小就是 8 - 5 = 3。

• 最坏情况下，是这两个子问题的较大者

• 由于在第 k 层扔下鸡蛋算作一次实验，k 的值在【1，k】

• 因此：

解释：

由于丢那一个鸡蛋需要记录一次操作，所以末尾要加上 1；
每一个新值的计算，都参考了比它行数少，列数少的值，这些值一定是之前已经计算出来的，这样的过程就叫做「状态转移」。

第3步：考虑初始化

• 一般而言，需要 0 这个状态的值，这里 0 层楼和 0 个鸡蛋是需要考虑进去的，它们的值会被后来的值所参考，并且也比较容易得到。

• 因此表格需要N+1行，K+1列

• 由于 F 值不会超过最大楼层的高度，要求的是最小值，因此初始化的时候，可以叫表格的单元格值设置成一个很大的数，但是这个数肯定也不会超过当前考虑的楼层的高度。

  • 第0行：楼层为0 的时候，不管鸡蛋个数多少，都测试不出鸡蛋的 F 值，故全为 0；
  • 第1行：楼层为1：如果0个鸡蛋，丢0次；一个鸡蛋，丢一次
  • 第0列：鸡蛋个数为 0 的时候，不管楼层为多少，也测试不出鸡蛋的 F 值，故全为 0，虽然不符合题意，但是这个值有效，它在后面的计算中会被用到；
  • 第1列：鸡蛋个数为 1 的时候，这是一种极端情况，要试出 F 值，最少次数就等于楼层高度；

第 4 步：考虑输出

输出就是表格的最后一个单元格的值 dp[N][K]。

Java

Solution :

import java.util.Arrays;

public class Solution {

    public int superEggDrop(int K, int N) {

        // dp[i][j]：一共有 i 层楼梯的情况下，使用 j 个鸡蛋的最少实验的次数
        // 注意：
        // 1、i 表示的是楼层的大小，不是第几层的意思，例如楼层区间 [8, 9, 10] 的大小为 3，这一点是在状态转移的过程中调整的定义
        // 2、j 表示可以使用的鸡蛋的个数，它是约束条件，我个人习惯放在后面的维度，表示消除后效性的意思

        // 0 个楼层和 0 个鸡蛋的情况都需要算上去，虽然没有实际的意义，但是作为递推的起点，被其它状态值所参考
        int[][] dp = new int[N + 1][K + 1];

        // 由于求的是最小值，因此初始化的时候赋值为一个较大的数，9999 或者 i 都可以
        for (int i = 0; i <= N; i++) {
            Arrays.fill(dp[i], i);
        }

        // 初始化：填写下标为 0、1 的行和下标为 0、1 的列
        // 第 0 行：楼层为 0 的时候，不管鸡蛋个数多少，都测试不出鸡蛋的 F 值，故全为 0
        for (int j = 0; j <= K; j++) {
            dp[0][j] = 0;
        }

        // 第 1 行：楼层为 1 的时候，0 个鸡蛋的时候，扔 0 次，1 个以及 1 个鸡蛋以上只需要扔 1 次
        dp[1][0] = 0;
        for (int j = 1; j <= K; j++) {
            dp[1][j] = 1;
        }

        // 第 0 列：鸡蛋个数为 0 的时候，不管楼层为多少，也测试不出鸡蛋的 F 值，故全为 0
        // 第 1 列：鸡蛋个数为 1 的时候，这是一种极端情况，要试出 F 值，最少次数就等于楼层高度（想想复杂度的定义）
        for (int i = 0; i <= N; i++) {
            dp[i][0] = 0;
            dp[i][1] = i;
        }

        // 从第 2 行，第 2 列开始填表
        for (int i = 2; i <= N; i++) {
            for (int j = 2; j <= K; j++) {
                for (int k = 1; k <= i; k++) {
                    // 碎了，就需要往低层继续扔：层数少 1 ，鸡蛋也少 1
                    // 不碎，就需要往高层继续扔：层数是当前层到最高层的距离差，鸡蛋数量不少
                    // 两种情况都做了一次尝试，所以加 1
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
                }
            }
        }
        return dp[N][K];
    }
}

复杂度分析：

• 时间复杂度：O(N^2 K)，三层 for 循环，每层循环都是线性的；
• 空间复杂度：O(NK)，表格的大小。

上面算法没问题，但因为力扣自己的问题，接下来要做一些时间复杂度的优化

优化

这里需要盯着「状态转移方程」看：

「状态转移方程」里最外层的变量是 k，它枚举了扔下鸡蛋的楼层的高度，这里它是自变量，将其余的 i 和 j 视为常数：

• dp[k - 1] [j - 1]：根据语义，k 增大的时候，楼层大小越大，它的值就越大；
• dp[i - k] [j]：根据语义，k 增大的时候，楼层大小越小，它的值就越小。

也就是找到使得 dp[i - k] [j] <= dp[k - i] [j - 1] 最大的那个 k 值即可。这里使用二分查找算法。关键在于 dp[i - k] [j] > dp[k - i] [j - 1] 的时候，k 一定不是我们要找的，根据这一点写出二分的代码。

import java.util.Arrays;

public class Solution {

    public int superEggDrop(int K, int N) {
        // dp[i][j]：一共有 i 层楼梯的情况下，使用 j 个鸡蛋的最少仍的次数
        int[][] dp = new int[N + 1][K + 1];
        
        // 初始化
        for (int i = 0; i <= N; i++) {
            Arrays.fill(dp[i], i);
        }
        for (int j = 0; j <= K; j++) {
            dp[0][j] = 0;
        }

        dp[1][0] = 0;
        for (int j = 1; j <= K; j++) {
            dp[1][j] = 1;
        }
        for (int i = 0; i <= N; i++) {
            dp[i][0] = 0;
            dp[i][1] = i;
        }

        // 开始递推
        for (int i = 2; i <= N; i++) {
            for (int j = 2; j <= K; j++) {
                // 在区间 [1, i] 里确定一个最优值
                int left = 1;
                int right = i;
                while (left < right) {
                    // 找 dp[k - 1][j - 1] <= dp[i - mid][j] 的最大值 k
                    int mid = left + (right - left + 1) / 2;
                    
                    int breakCount = dp[mid - 1][j - 1];
                    int notBreakCount = dp[i - mid][j];
                    if (breakCount > notBreakCount) {
                        // 排除法（减治思想）写对二分见第 35 题，先想什么时候不是解
                        // 严格大于的时候一定不是解，此时 mid 一定不是解
                        // 下一轮搜索区间是 [left, mid - 1]
                        right = mid - 1;
                    } else {
                        // 这个区间一定是上一个区间的反面，即 [mid, right]
                        // 注意这个时候取中间数要上取整，int mid = left + (right - left + 1) / 2;
                        left = mid;
                    }
                }
                // left 这个下标就是最优的 k 值，把它代入转移方程 Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1) 即可
                dp[i][j] = Math.max(dp[left - 1][j - 1], dp[i - left][j]) + 1;
            }
        }
        return dp[N][K];
    }
}

Python

Solution :

打赏