鸡蛋掉落问题_鸡蛋掉落问题 csdn

class Solution {
public:
    int superEggDrop(int k, int n)
    {
        vector<vector<int>>dp(n+1,vector<int>(k+1,INT_MAX));
        //1个鸡蛋，n层楼，最坏都需要n次。
        for(int i=1;i<=n;i++)
        {
            dp[i][1]=i;
        }
        //0层楼，k个鸡蛋，需要0次；1层楼，k个鸡蛋，需要1次。
        for(int i = 1;i<=k;i++)
        {
            dp[0][i] = 0;
            dp[1][i] = 1;
        }
        
        for(int i = 2;i<=n;i++)
        {
            for(int j = 2;j<=k;j++)
            {
                for(int a = 1;a<=i;a++)
                {
                    int temp = max(dp[a-1][j-1],dp[i-a][j])+1;
                    dp[i][j] = min(temp,dp[i][j]);
                }
            }
        }
        return dp[n][k];
    }
};