这题面试大概率能遇上,直接上最优解吧。
这道题最优解的特点在于它是反过来理解提干的:原问题是N层楼K个棋子最少扔多少次,现在反过来看,如果有K个棋子,能扔M次,能搞定多少层楼。
row:次数; col:棋子数 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
2 | 0 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 |
3 | 0 | 1 | 3 | 7 | 14 | 25 | 41 | 63 | 92 | 129 | 175 |
4 | 0 | 1 | 3 | 7 | 15 | 30 | 56 | 98 | 162 | 255 | 385 |
5 | 0 | 1 | 3 | 7 | 15 | 31 | 62 | 119 | 218 | 381 | 637 |
实现推理表:
int superEggDrop(int K, int N){
if(K<1||N<1){
return 0;
}
int binSearchK=log(N);
if(K>binSearchK+1){
return binSearchK;
}
vector<vector<int>> dp(K+1,vector<int>(N+1,0));
for(int i=1;i<=K;++i){
dp[i][1]=1; //第一列全为1
}
for(int j=2;j<=N;++j){
for(int i=1;i<=K;++i){
dp[i][j]=dp[i][j-1]+dp[i-1][j-1]+1;
if(dp[i][j]>=N){
return j;
}
}
}
return 0;
}
int log(int n){
int ret=0;
while(n>0){
ret++;
n=n/2;
}
return ret;
}