問(wèn)題定義
原始題目來(lái)源于LeetCode https://leetcode-cn.com/problems/super-egg-drop/comments/
你將獲得 K 個(gè)雞蛋坎背，并可以使用一棟從 1 到 N 共有 N 層樓的建筑索抓。
每個(gè)蛋的功能都是一樣的，如果一個(gè)蛋碎了必盖，你就不能再把它掉下去减噪。
你知道存在樓層 F ，滿足 0 <= F <= N 任何從高于 F 的樓層落下的雞蛋都會(huì)碎轿秧，從 F 樓層或比它低的樓層落下的雞蛋都不會(huì)破桥嗤。
每次移動(dòng)，你可以取一個(gè)雞蛋（如果你有完整的雞蛋）并把它從任一樓層 X 扔下（滿足 1 <= X <= N）埂伦。
你的目標(biāo)是確切地知道 F 的值是多少煞额。
無(wú)論 F 的初始值如何，你確定 F 的值的最小移動(dòng)次數(shù)是多少赤屋？
示例 1：
輸入：K = 1, N = 2
輸出：2
解釋：
雞蛋從 1 樓掉落立镶。如果它碎了，我們肯定知道 F = 0 类早。
否則媚媒，雞蛋從 2 樓掉落。如果它碎了涩僻，我們肯定知道 F = 1 缭召。
如果它沒(méi)碎，那么我們肯定知道 F = 2 逆日。
因此嵌巷，在最壞的情況下我們需要移動(dòng) 2 次以確定 F 是多少。
示例 2：
輸入：K = 2, N = 6
輸出：3
示例 3：
輸入：K = 3, N = 14
輸出：4
提示：
1 <= K <= 100
1 <= N <= 10000
問(wèn)題解析
第一反應(yīng)室抽，二分法搪哪。但是雞蛋數(shù)量是有限的。比如K=2坪圾，N=6的情況晓折。第一次先扔3樓，3樓如果沒(méi)碎兽泄，則在4-6樓中繼續(xù)試驗(yàn)漓概；3樓碎了的話，則只能從1樓開(kāi)始進(jìn)行病梢，最多次數(shù)3胃珍。
不過(guò)，不適合用于雞蛋數(shù)量少，樓層高的情況觅彰。比如K=2吩蔑，N=50的情況。第一次扔25樓填抬，如果碎了哥纫，就必須從1樓還是扔。則最多有25次痴奏。如果第一次扔10樓，不碎的話扔20樓厌秒，一直到40樓读拆，這樣最多的次數(shù)為4+10=14次⊥疑粒可見(jiàn)檐晕，直接二分的方法不通用。按照幾等分的方法也不通用蚌讼。
第二反應(yīng)辟灰，動(dòng)態(tài)規(guī)劃。和背包問(wèn)題有些像篡石，也是基于上一個(gè)條件來(lái)得出最優(yōu)解芥喇。本題的關(guān)鍵點(diǎn)就轉(zhuǎn)換為找到狀態(tài)轉(zhuǎn)移方程，以及結(jié)束條件凰萨。
狀態(tài)轉(zhuǎn)移方程
使用 dp(K,N) 表示狀態(tài)轉(zhuǎn)移继控，表示在有 K 個(gè)雞蛋，N樓時(shí)候需要扔雞蛋的次數(shù)胖眷。如果在第 i 層扔雞蛋武通。
- 雞蛋碎了，在 dp(K-1, i -1) 中找最大值珊搀。即現(xiàn)在剩余雞蛋數(shù)目 -1 冶忱，查找 i 層以下的樓層
- 雞蛋沒(méi)碎，在 dp(K , N - i) 中找最大值境析。即現(xiàn)在剩余雞蛋數(shù)不變囚枪，查找 i ~ N層之間的樓層，即 i+1, i+2, 到 N簿晓，總樓層數(shù)為 N - i
- 于是可以得到狀態(tài)轉(zhuǎn)移方程如下所示：
dp(k,N) = max(dp(K -1, i-1), dp(K, N - i) + 1 );
結(jié)束條件
狀態(tài)的終止條件:
- 只有1個(gè)雞蛋了眶拉，還有多少層沒(méi)測(cè)完就還需要扔多少次
- 樓層全部測(cè)完了，不管還剩幾個(gè)雞蛋都結(jié)束
-
于是可以得出結(jié)束條件有兩個(gè)
if (N ==0) {
dp(k,N) = 0;
} else if (K == 1) {
dp(k,N) = N;
}
這種做法有點(diǎn)像數(shù)學(xué)歸納法的證明方式憔儿。
egg_drop.jpg
時(shí)間復(fù)雜度
由于不知道起始扔雞蛋的位置忆植，所以在設(shè)置起始位置時(shí)候，需要遍歷來(lái)進(jìn)行查找。
所以 動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度 = N * dp（K,N)朝刊，其中 dp 為一個(gè)循環(huán)耀里，即O（N），最后得到的復(fù)雜度為 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 - 狀態(tài)轉(zhuǎn)移函數(shù)
* @K: 雞蛋個(gè)數(shù)
* @N: 總共樓層
*
* return: 需要扔雞蛋次數(shù)
*/
int dp(int K, int N)
{
int i, ret, cnt;
ret = 0;
/* 最開(kāi)始扔雞蛋位置不確定,需要遍歷 */
for (i = 1; i <= N; i++) {
/**
* dp(K - 1, i - 1) 為雞蛋碎了后,用K-1個(gè)雞蛋測(cè)i-1層樓
* dp(K, N - i) 為雞蛋沒(méi)碎后,用K個(gè)雞蛋測(cè)(i - 1)層樓
* +1 表示已經(jīng)扔了一次,次數(shù)++
*/
cnt = max(dp(K - 1, i - 1), dp(K, N - i)) + 1; /* 最壞情況下的次數(shù) */
if (i == 1) {
ret = cnt;
} else {
ret = min(ret, cnt); /* 查找不同樓層丟,找到丟次數(shù)最少的樓層,即找到最少次數(shù) */
}
}
return ret;
}
/**
* superEggDrop - 獲取最小扔雞蛋次數(shù)
* @K: 雞蛋個(gè)數(shù)
* @N: 總共樓層
*
* return: 需要扔雞蛋次數(shù)
*/
int superEggDrop(int K, int N)
{
int i, ret, cnt;
ret = 0;
if (N == 0) { /* 到最低層,不需要再扔雞蛋了 */
return 0;
} else if (K == 1) { /* 雞蛋只有一個(gè),有幾層最多扔幾次雞蛋 */
return N;
}
/* 最開(kāi)始扔雞蛋位置不確定,需要遍歷 */
for (i = 1; i <= N; i++) {
/* 第一次從i層丟下后,需要的次數(shù) */
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;
/* 打樁驗(yàn)證 */
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
執(zhí)行效果
./egg_drop
superEggDrop ret:4
