力扣887题：用动态规划算法解决鸡蛋掉落问题

一、题目解读

力扣887题目：给定K个鸡蛋和N层楼，通过最少的扔鸡蛋次数确定鸡蛋摔碎的临界楼层F（F≤N）。需输出最小扔鸡蛋次数。题目难点在于如何通过有限鸡蛋测试所有可能楼层，并找到最优策略。

二、解题思路

用动态规划（DP）求解。核心思想：定义状态dp[m][k]为m次操作和k个鸡蛋能确定的最大楼层数。通过推导状态转移方程，逐层递进计算最优解。关键在于理解“鸡蛋碎与不碎”的分支情况对后续测试层数的影响。

三、解题步骤

1. 状态定义：dp[m][k]表示m次操作、k个鸡蛋能检测的最大楼层。

2. 边界处理：初始化dp[0][k]=0（无操作无法检测），dp[m][1]=m（仅1个鸡蛋需逐层测试）。

3. 状态转移推导：

○ 若第m次操作鸡蛋碎：剩余m-1次操作和k-1个鸡蛋，可检测dp[m-1][k-1]层；

○ 若鸡蛋未碎：剩余m-1次操作和k个鸡蛋，可检测dp[m-1][k]层；

○ 总可检测层数为两者之和+当前层，即dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1。

4. 循环求解：从m=1开始递增，直至dp[m][K]≥N，此时m即为最小次数。

四、代码与注释

class Solution {
public:
    int superEggDrop(int k, int n) {
        // dp[m][k]表示k个鸡蛋m次操作能确定的最大楼层数
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        
        int m = 0; // 操作次数
        while (dp[m][k] < n) { // 当可检测层数不足N时，递增m
            m++;
            for (int i = 1; i <= k; ++i) { // 更新各状态
                // 状态转移方程：dp[m][i] = dp[m-1][i-1] + dp[m-1][i] + 1
                dp[m][i] = dp[m-1][i-1] + dp[m-1][i] + 1;
            }
        }
        return m; // 返回最小操作次数
    }
};

五、总结

1. 算法核心：动态规划通过子问题最优解推导全局解，状态转移方程基于“碎与不碎”的二进制决策。

2. 优化方向：原解法时间复杂度为O(KN)，可进一步优化至O(KlogN)或利用数学公式推导（如等差数列求和）。

3. 实际应用：适用于资源受限的决策问题，如测试成本最小化场景。

4. 关键点：理解状态定义与转移逻辑，避免陷入暴力递归的误区。