【leetcode】鸡蛋掉落问题

在leetcode刷动态规划问题过程中，鸡蛋掉落问题是比较经典的，特别是笔试面试喜欢出的问题。腾讯，Vivo等大厂都出现过，在这里通过自己学习，以及借鉴大佬的思路，对这道题进行整理。

其它算法问题刷题总结可以参考：基础算法分类总结（持续更新中）。

一、鸡蛋掉落问题解析

1. 题目描述

leetcode题目链接：887. 鸡蛋掉落

2. 解决方法

遇到这个问题时，很多同学就觉得使用二分查找，不断缩减查找的区间。但直接使用二分查找去计算层数时，鸡蛋是不够的。题目中描述说，每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。可以分析发现：

一颗蛋在任一楼层扔下，分两种情况：

1. 蛋碎了。也就是说需要向下尝试楼层。剩余蛋个数为K-1个，剩余可尝试次数为f-1次
2. 蛋没碎。也就是说可以向上继续尝试楼层。剩下的蛋个数为K个，剩余可尝试次数为f-1次

因此可以使用动态规划来解决这道问题。

2.1 动态规划——01背包——二维数组

鸡蛋掉落的问题可以理解为动态规划中典型的01背包问题。背包：鸡蛋数（k个）； 物品：操作数（n个）；价值：确定楼层。01背包问题可以参考：动态规划之背包问题——01背包。

有人问了，为什么不是鸡蛋作为物品，操作数作为背包？背包问题往往物品与价值有正相关关系。鸡蛋有k个，但实际不一定全都用上，限制一定的最小操作数，鸡蛋增加，确定楼层（价值）不一定增加。而取一定的鸡蛋，操作数每增加1，确定楼层(价值)就会一定增加。

因此可以定义：dp[i][count]代表k个鸡蛋扔count层最多能测试层数。

状态转移方程：当前价值 = 鸡蛋碎了的价值 + 鸡蛋没碎的价值 + 确定当前层的价值1，dp[i][count] = dp[i-1][count-1]+dp[i][count-1]+1;

这样二维数组的01背包解法的如下（二维01背包的遍历顺序都可以）：

class Solution {
   
    public int superEggDrop(int k, int n) {
   
        // 动态规划01背包,dp[i][count]代表k个鸡蛋扔count层最多能测试层数
        // 当前价值 = 鸡蛋碎了的价值 + 鸡蛋没碎的价值 + 确定当前层的价值1
        // dp[i][count] = dp[i-1][count-1]+dp[i][count-1]+1;
        // 背包：鸡蛋数（k个）； 物品：操作数（n个）；价值：确定楼层
        if (n == 1) return 1;
        int[][] dp = new int[k + 1][n + 1];
        int count = 0;
        for (
1
2
3
4
5
6
7
8
9
10
11