鸡蛋掉落问题解析

问题定义

原始题目来源于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 层扔鸡蛋。

1. 鸡蛋碎了，在 dp(K-1, i -1) 中找最大值。即现在剩余鸡蛋数目 -1 ，查找 i 层以下的楼层
2. 鸡蛋没碎，在 dp(K , N - i) 中找最大值。即现在剩余鸡蛋数不变，查找 i ~ N层之间的楼层，即 i+1, i+2, 到 N，总楼层数为 N - i
3. 于是可以得到状态转移方程如下所示：
   dp(k,N) = max(dp(K -1, i-1), dp(K, N - i) + 1 );

结束条件

状态的终止条件:

1. 只有1个鸡蛋了，还有多少层没测完就还需要扔多少次
2. 楼层全部测完了，不管还剩几个鸡蛋都结束

3. 于是可以得出结束条件有两个
   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