1 问题描述
有 T 层楼，n个鸡蛋，鸡蛋是相同的，临界楼层是指从某个楼层之上抛下来，都会碎，但从这个楼层之下抛下来，都不会碎。没有碎的鸡蛋可以重复使用。试假设能找到这个临界楼层需要抛投的最少次数。
T层，n个鸡蛋, 总是先要任选一层k, 扔下一个鸡蛋；扔下之后有两个结果：
- 没碎: 则需要在高层求解 F(T-k, n)
- 碎了: 则在k层以下求解 F(k-1, n-1)
假设我们在第 k 层扔下第一个鸡蛋，最坏的情况下，我们需要扔多少次：
cost(k, T, n) = max{F(T-k, n), F(k-1, n-1)} + 1
我们把每一层，遍历一下最坏情况下所有方案的，最少扔鸡蛋的次数：
F(T, n) = min{cost(1, T, n), cost(2, T, n), …, cost(k, T, n), …, cost(T, T, n)}
2 实现
简单一点，我们直接采用递归求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#define INF (1<<30)
int F(int T, int egg);
int G_Cache[1000][20];
//方法一：递归求解(记忆化)
int cost(int k, int T, int egg)
{
return std::max(F(T-k, egg), F(k-1, egg-1)) + 1;
}
int F(int T, int egg) {
// only 1 egg, return layers
if (egg == 1) {
return T;
}
// 0 layer or 1 layer
if (T == 0 || T == 1) {
return T;
}
//命中缓存
if (G_Cache[T][egg]) {
return G_Cache[T][egg];
}
int ans = INF;
for(int k = 1; k<=T; ++k) {
int times = cost(k, T, egg);
ans = std::min(ans, times);
}
//加入缓存
G_Cache[T][egg] = ans;
return ans;
}
//递归求解(记忆化递归)
void TestRecursive(){
memset(G_Cache, 0, sizeof(G_Cache));
// 100 layer, 2 eggs, 最多只需要 14 times
int times = F(100, 2);
printf("%d\n", times);
}
/**
* 方法二： 递推求解
* T层，N个鸡蛋，最多需要扔多少次
* -使用递推公式, 打表求解:
* -时间复杂度 O(T*T*N)
* -空间复杂度 O(T*N)
* x当然空间，还可以进一步优化，我们发现递推公式,鸡蛋只有 egg/egg-1,
* x每次计算只前一列+当前列有关， 使用滚动数组进行优化：
* O(2T)
*/
int Derivate(int T, int egg_size)
{
const int ROW = T + 2;// 楼层
const int COL = egg_size + 2;//鸡蛋个数
const int MAX_INF = 0x7f7f7f7f;
// 二维数组 dp[ROW][COL],每个元素初始化为 MAX_INF
vector<vector<int>> dp(ROW, vector<int>(COL, MAX_INF));
// 0层,只需要0次
for(int z = 0; z <= egg_size; z++){ dp[0][z] = 0;}
// 1层, n>=1个蛋都只需要1次
for(int z = 1; z <= egg_size; z++){ dp[1][z] = 1;}
// 1个蛋，k层就需要k次(只能每一层去测试)
for(int k = 1; k <= T; k++){ dp[k][1] = k;}
for (int egg = 2; egg <= egg_size; egg++) {
for (int t = 2; t <= T; t++) {
//min_cost 表示T层，N个鸡蛋，最少需要扔多少次
int min_cost = MAX_INF;
for (int k = 1; k <= t; k++) {
int times = std::max(dp[t - k][egg], dp[k - 1][egg - 1]) + 1;
min_cost = std::min(min_cost, times);
}
dp[t][egg] = min_cost;
}
}
return dp[T][egg_size];
}
//方法二： 递推求解
void TestDerivate() {
// 100 layer, 2 eggs, 最多只需要 14 times
int times = Derivate(100, 2);
printf("%d\n", times);
}
int main()
{
TestDerivate();
return 0;
}
|
总结
很多问题我们需要先分析，简单情况; 将复杂的问题划分为更小的问题，
如果问题还不可解，继续划分；直到划分为最简单的场景。
这种将大化小, 逐个击破的思路，在解决问题上非常有用。
因为复杂问题，都可看出许多小问题的组合；一旦我们掌握了这种思维方式，很多问题就可以迎刃而解了。
比如, 多个点的最小外接圆问题, 背包问题, 海盗分金币问题；都可以用这种思路求解。
参考