力扣1884题：从鸡蛋掉落问题理解动态规划

一、问题理解

题目描述：有2个相同的鸡蛋和一栋n层的楼，我们需要找到一个临界楼层f，使得鸡蛋从f层或更低层落下不会碎，而从高于f的楼层落下会碎。我们的目标是找到确定f的最小操作次数。

二、解题思路

1. ‌暴力解法‌：最直观的方法是线性搜索，从第1层开始一层层试，最坏情况下需要n次尝试。

2. ‌二分搜索‌：如果鸡蛋数量无限，可以用二分法，时间复杂度O(logn)。但本题只有2个鸡蛋，二分法在最坏情况下不是最优解。

3. ‌动态规划‌：这是最优解法。我们可以定义状态dp[k][m]表示用k个鸡蛋和m次尝试最多能确定的楼层数。

三、动态规划详解

状态转移方程：
dp[k][m] = dp[k-1][m-1] (鸡蛋碎了) + dp[k][m-1] (鸡蛋没碎) + 1 (当前楼层)

解释：

• 如果在x层扔鸡蛋：

• 碎了：用k-1个鸡蛋和m-1次尝试检查下面的x-1层

• 没碎：用k个鸡蛋和m-1次尝试检查上面的n-x层

• 所以总楼层数为两种情况之和加1

四、代码实现

class Solution {
public:
    int twoEggDrop(int n) {
        // dp[k][m] = n 表示k个鸡蛋扔m次最多可以确定的楼层数
        // 对于本题，k固定为2
        int eggs = 2;
        vector<vector<int>> dp(eggs + 1, vector<int>(n + 1, 0));
        
        int m = 0;
        while (dp[eggs][m] < n) {
            m++;
            for (int k = 1; k <= eggs; k++) {
                // 状态转移方程：
                // 如果在某层扔鸡蛋，有两种可能：
                // 1. 鸡蛋碎了，那么需要检查下面的楼层，用k-1个鸡蛋和m-1次机会
                // 2. 鸡蛋没碎，可以检查上面的楼层，用k个鸡蛋和m-1次机会
                // 所以总楼层数为两种情况之和加1（当前测试的楼层）
                dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1;
            }
        }
        
        return m;
    }
};

五、数学解法

这个问题也可以用数学方法解决。对于2个鸡蛋，最优策略是第一次在第x层扔，如果碎了就线性检查1到x-1层；如果没碎，第二次在x+(x-1)层扔，依此类推。解方程x+(x-1)+(x-2)+...+1 >= n可以得到x的值。