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

一、题目解读

力扣1884题要求解决经典的“鸡蛋掉落”问题：给定一座n层楼，你有2个鸡蛋，需要找出在最坏情况下，用最少次数确定鸡蛋摔不碎的最高楼层。题目核心在于通过二分或动态规划策略，优化测试次数，避免盲目尝试。

二、解题思路

采用动态规划策略。定义状态dp[k][m]为k个鸡蛋在m次投掷中能确定的最大楼层数，由于鸡蛋数量固定为2，代码简化了维度。通过迭代次数m，逐步计算每个状态值，直至满足dp[2][m] >= n。关键在于状态转移方程的推导：每次投掷后，鸡蛋可能碎（剩余k-1个鸡蛋和m-1次机会）或不碎（保持k个鸡蛋和m-1次机会），总楼层数为两种情况覆盖范围之和加当前测试楼层。

三、解题步骤

1. 初始化：创建二维dp数组（2个鸡蛋，最大n次投掷），初始值全为0。

2. 循环终止条件：当dp[2][m]首次大于等于n时停止迭代。

3. 状态转移计算：

    外层循环m递增，内层遍历k（1到2）。

    状态方程：dp[k][m] = dp[k-1][m-1]（碎）+ dp[k][m-1]（不碎）+ 当前层。

4. 结果返回：最终m即为最少投掷次数。

四、代码与注释

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;
    }
};

注释说明：代码通过动态规划构建状态转移矩阵，利用鸡蛋碎与不碎的两分支情况，逐步扩大可覆盖楼层数，最终确定最小测试次数。

五、总结

本文通过动态规划方法解析力扣1884题，核心在于将问题分解为子状态，并通过状态转移方程高效计算。关键点包括：

1. 明确状态定义（dp[k][m]的多维度含义）；

2. 推导碎与不碎的两分支决策影响；

3. 利用迭代避免递归性能损耗。

该思路对类似“资源受限的最优决策”问题具有通用性。