丢鸡蛋问题的 DP 解法
解法1:
-
状态表示:
f[i, j]
表示i
层楼,j
个鸡蛋检测出鸡蛋硬度(碎掉的临界楼层)需要的最少次数。 -
状态转移:
- 不使用第
j
个鸡蛋,则f[i, j] = f[i, j-1]
; - 使用第
j
个鸡蛋,则1 ~ i
层中共i
种可扔的情况,假设在第k
层扔:- 碎:搜索区间变为
1 ~ k-1
,最小次数由f[k-1, j-1]
给出; - 不碎:搜索区间变为
k+1 ~ j
,第j
个鸡蛋可重复利用,最小次数由f[i-k, j]
给出;
- 碎:搜索区间变为
- 枚举扔的楼层
k
;
#include <iostream>
using namespace std;
const int N = 110, M = 12;
int f[N][M];
int n, m;
int main(){
while(cin >> n >> m ){ // ~scanf("%d%d", &n, &m)
for(int i = 1; i <= n; i ++) f[i][1] = i;
for(int j = 1; j <= m; j ++) f[1][j] = 1;
for(int i = 2; i <= n; i ++){
for(int j = 2; j <= m; j ++){
f[i][j] = f[i][j-1];
for(int k = 1; k <= i; k ++){
f[i][j] = min(f[i][j], max(f[k-1][j-1], f[i-k][j]) + 1);
}// j-1 个蛋或许已经够用,取最小 // 取最大是因为要考虑最坏情况
}
}
cout << f[n][m] << endl;
}
}
解法2:
f[i, j]
表示用j
个鸡蛋扔i
次能测试出的区间长度的最大值。- 状态转移:
- 在某位置扔第
j
个鸡蛋后,蛋碎,那么接下来还有j-1
个蛋,i-1
次:f[i-1, j-1]
。 - 蛋不碎:
f[i-1][j]
。 - 注意:碎和不碎是不同的情况,二者计算的最长区间没有交集,因此
f[i, j] = f[i-1, j] + f[i-1, j-1] + 1
。
#include <iostream>
using namespace std;
const int N = 110, M = 12;
int f[N][M];
int n, m;
int main(){
while(cin >> n >> m){
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++)
f[i][j] = f[i-1][j-1] + f[i-1][j] + 1;
if(f[i][m] >= n){
cout << i << endl;
break;
}
}
}
}
-