题面：
题解：
解法一：
#include<algorithm>
using namespace std;
class Solution {
//dp[i][j] i个鸡蛋测试j层高的楼需要的最少测试次数
int dp[110][10100];
//则有dp[i][j]=min( 1+max(dp[i-1][k-1],dp[i][j-k]) k in [1,j])
//从第k层楼扔下一个鸡蛋
//如果破了，手里有i-1个鸡蛋，测试k-1层楼
//如果没破，手里有i个鸡蛋，测试j-k层楼
//时间复杂度O(k*n*n)
public:
int superEggDrop(int k, int n) {
//最坏步数
for(int i=0;i<=k;i++)
{
for(int j=0;j<=n;j++)
dp[i][j]=j;
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
for(int tmp=1;tmp<=j;tmp++)
{
//如果还剩0个鸡蛋，则只能测试0层
if(i-1>0||tmp-1==0)
dp[i][j]=min(dp[i][j],1+max(dp[i-1][tmp-1],dp[i][j-tmp]));
}
}
}
return dp[k][n];
}
};解法二：
#include<algorithm>
using namespace std;
class Solution {
//dp[i][j] i个鸡蛋测试j次最高可以测试dp[i][j]层楼高
//在i个鸡蛋dp[i][j]楼高的情况下，最少需要j次才可以找到f的确切的值
//若楼更高或者鸡蛋更少，则需要更多的测试次数
//因为在最坏的情况下，1个鸡蛋测试n次则可以测试出n层楼，则最多不超过n次
int dp[110][10100];
//则有dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1
//dp[i-1][j-1] i-1个鸡蛋测j-1次
//dp[i][j-1] i个鸡蛋测j-1次
//+1表示本次测试测出一层楼高度
//假设现在楼高dp[i][j]
//进行第一次测试，在第x层
//如果摔破了，则还可以测dp[i-1][j-1]
//如果没摔破，则还可以测dp[i][j-1]
//我们不关心x是在哪一层，但是我们知道，在x层扔可以取得最优解dp[i][j]
//初始值
//dp[i][1]=1
//dp[1][j]=j
//时间复杂度O(k*n)
public:
int superEggDrop(int k, int n) {
for(int i=1;i<=k;i++)
dp[i][1]=1;
for(int j=1;j<=n;j++)
dp[1][j]=j;
for(int i=2;i<=k;i++)
{
for(int j=2;j<=n;j++)
{
//会爆掉int
dp[i][j]=min(n,dp[i-1][j-1]+dp[i][j-1]+1);
}
}
for(int j=0;j<=n;j++)
if(dp[k][j]>=n) return j;
return 0;
}
};