问题定义
原始题目来源于LeetCode https://leetcode-cn.com/problems/super-egg-drop/comments/
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
示例 1：
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2：
输入：K = 2, N = 6
输出：3
示例 3：
输入：K = 3, N = 14
输出：4
提示：
1 <= K <= 100
1 <= N <= 10000
问题解析
第一反应，二分法。但是鸡蛋数量是有限的。比如K=2，N=6的情况。第一次先扔3楼，3楼如果没碎，则在4-6楼中继续试验；3楼碎了的话，则只能从1楼开始进行，最多次数3。
不过，不适合用于鸡蛋数量少，楼层高的情况。比如K=2，N=50的情况。第一次扔25楼，如果碎了，就必须从1楼还是扔。则最多有25次。如果第一次扔10楼，不碎的话扔20楼，一直到40楼，这样最多的次数为4+10=14次。可见，直接二分的方法不通用。按照几等分的方法也不通用。
第二反应，动态规划。和背包问题有些像，也是基于上一个条件来得出最优解。本题的关键点就转换为找到状态转移方程，以及结束条件。
状态转移方程
使用 dp(K,N) 表示状态转移，表示在有 K 个鸡蛋，N楼时候需要扔鸡蛋的次数。如果在第 i 层扔鸡蛋。
- 鸡蛋碎了，在 dp(K-1, i -1) 中找最大值。即现在剩余鸡蛋数目 -1 ，查找 i 层以下的楼层
- 鸡蛋没碎，在 dp(K , N - i) 中找最大值。即现在剩余鸡蛋数不变，查找 i ~ N层之间的楼层，即 i+1, i+2, 到 N，总楼层数为 N - i
- 于是可以得到状态转移方程如下所示：
dp(k,N) = max(dp(K -1, i-1), dp(K, N - i) + 1 );
结束条件
状态的终止条件:
- 只有1个鸡蛋了，还有多少层没测完就还需要扔多少次
- 楼层全部测完了，不管还剩几个鸡蛋都结束
-
于是可以得出结束条件有两个
if (N ==0) {
dp(k,N) = 0;
} else if (K == 1) {
dp(k,N) = N;
}
这种做法有点像数学归纳法的证明方式。
egg_drop.jpg
时间复杂度
由于不知道起始扔鸡蛋的位置，所以在设置起始位置时候，需要遍历来进行查找。
所以 动态规划的时间复杂度 = N * dp（K,N)，其中 dp 为一个循环，即O（N），最后得到的复杂度为 O（N^2）。
代码
egg_drop.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#define min(x,y) ({ typeof(x) _x = (x); typeof(y) _y = (y); (void) (&_x == &_y); _x < _y ? _x : _y; })
#define max(x,y) ({ typeof(x) _x = (x); typeof(y) _y = (y); (void) (&_x == &_y); _x > _y ? _x : _y; })
/**
* dp - 状态转移函数
* @K: 鸡蛋个数
* @N: 总共楼层
*
* return: 需要扔鸡蛋次数
*/
int dp(int K, int N)
{
int i, ret, cnt;
ret = 0;
/* 最开始扔鸡蛋位置不确定,需要遍历 */
for (i = 1; i <= N; i++) {
/**
* dp(K - 1, i - 1) 为鸡蛋碎了后,用K-1个鸡蛋测i-1层楼
* dp(K, N - i) 为鸡蛋没碎后,用K个鸡蛋测(i - 1)层楼
* +1 表示已经扔了一次,次数++
*/
cnt = max(dp(K - 1, i - 1), dp(K, N - i)) + 1; /* 最坏情况下的次数 */
if (i == 1) {
ret = cnt;
} else {
ret = min(ret, cnt); /* 查找不同楼层丢,找到丢次数最少的楼层,即找到最少次数 */
}
}
return ret;
}
/**
* superEggDrop - 获取最小扔鸡蛋次数
* @K: 鸡蛋个数
* @N: 总共楼层
*
* return: 需要扔鸡蛋次数
*/
int superEggDrop(int K, int N)
{
int i, ret, cnt;
ret = 0;
if (N == 0) { /* 到最低层,不需要再扔鸡蛋了 */
return 0;
} else if (K == 1) { /* 鸡蛋只有一个,有几层最多扔几次鸡蛋 */
return N;
}
/* 最开始扔鸡蛋位置不确定,需要遍历 */
for (i = 1; i <= N; i++) {
/* 第一次从i层丢下后,需要的次数 */
cnt = max(dp(K, N - i), dp(K - 1, i - 1)) + 1;
if (i == 1) {
ret = cnt;
} else {
ret = min(ret, cnt);
}
}
return ret;
}
int main (int argc, char *argv[])
{
int K, N;
int ret;
/* 打桩验证 */
K = 3;
N = 14;
ret = superEggDrop(K, N);
printf("superEggDrop ret:%d\n", ret);
return ret;
}
Makefile：
CC = gcc
CFLAGS = -g
LIBS = -lrt
ELF = egg_drop
SRC1 = egg_drop.c
OBJ1 = $(SRC1:%.c=%.o)
all: ${ELF}
egg_drop: $(OBJ1)
${CC} ${CFLAGS} -o $@ $^ ${LIBS}
$(OBJ1): %.o: %.c
${CC} ${CFLAGS} -c -o $@ $<
clean:
rm -f ${ELF} *.o *.d
执行效果
./egg_drop
superEggDrop ret:4
