讀完本文，你可以去力扣拿下如下題目：
-----------
今天要聊一個(gè)很經(jīng)典的算法問題，若干層樓，若干個(gè)雞蛋，讓你算出最少的嘗試次數(shù)，找到雞蛋恰好摔不碎的那層樓。國內(nèi)大廠以及谷歌臉書面試都經(jīng)常考察這道題，只不過他們覺得扔雞蛋太浪費(fèi)，改成扔杯子，扔破碗什么的。
具體的問題等會(huì)再說，但是這道題的解法技巧很多，光動(dòng)態(tài)規(guī)劃就好幾種效率不同的思路，最后還有一種極其高效數(shù)學(xué)解法。秉承咱們號一貫的作風(fēng)，拒絕奇技淫巧，拒絕過于詭異的技巧，因?yàn)檫@些技巧無法舉一反三，學(xué)了也不劃算。
下面就來用我們一直強(qiáng)調(diào)的動(dòng)態(tài)規(guī)劃通用思路來研究一下這道題。
一、解析題目
題目是這樣：你面前有一棟從 1 到 N 共 N 層的樓，然后給你 K 個(gè)雞蛋（K 至少為 1）。現(xiàn)在確定這棟樓存在樓層 0 <= F <= N，在這層樓將雞蛋扔下去，雞蛋恰好沒摔碎（高于 F 的樓層都會(huì)碎，低于 F 的樓層都不會(huì)碎）?，F(xiàn)在問你，最壞情況下，你至少要扔幾次雞蛋，才能確定這個(gè)樓層 F 呢？
也就是讓你找摔不碎雞蛋的最高樓層 F，但什么叫「最壞情況」下「至少」要扔幾次呢？我們分別舉個(gè)例子就明白了。
比方說現(xiàn)在先不管雞蛋個(gè)數(shù)的限制，有 7 層樓，你怎么去找雞蛋恰好摔碎的那層樓？
最原始的方式就是線性掃描：我先在 1 樓扔一下，沒碎，我再去 2 樓扔一下，沒碎，我再去 3 樓……
以這種策略，最壞情況應(yīng)該就是我試到第 7 層雞蛋也沒碎（F = 7），也就是我扔了 7 次雞蛋。
先在你應(yīng)該理解什么叫做「最壞情況」下了，雞蛋破碎一定發(fā)生在搜索區(qū)間窮盡時(shí)，不會(huì)說你在第 1 層摔一下雞蛋就碎了，這是你運(yùn)氣好，不是最壞情況。
現(xiàn)在再來理解一下什么叫「至少」要扔幾次。依然不考慮雞蛋個(gè)數(shù)限制，同樣是 7 層樓，我們可以優(yōu)化策略。
最好的策略是使用二分查找思路，我先去第 (1 + 7) / 2 = 4 層扔一下：
如果碎了說明 F 小于 4，我就去第 (1 + 3) / 2 = 2 層試……
如果沒碎說明 F 大于等于 4，我就去第 (5 + 7) / 2 = 6 層試……
以這種策略，最壞情況應(yīng)該是試到第 7 層雞蛋還沒碎（F = 7），或者雞蛋一直碎到第 1 層（F = 0）。然而無論那種最壞情況，只需要試 log7 向上取整等于 3 次，比剛才嘗試 7 次要少，這就是所謂的至少要扔幾次。
PS：這有點(diǎn)像 Big O 表示法計(jì)算?算法的復(fù)雜度。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
實(shí)際上，如果不限制雞蛋個(gè)數(shù)的話，二分思路顯然可以得到最少嘗試的次數(shù)，但問題是，現(xiàn)在給你了雞蛋個(gè)數(shù)的限制 K，直接使用二分思路就不行了。
比如說只給你 1 個(gè)雞蛋，7 層樓，你敢用二分嗎？你直接去第 4 層扔一下，如果雞蛋沒碎還好，但如果碎了你就沒有雞蛋繼續(xù)測試了，無法確定雞蛋恰好摔不碎的樓層 F 了。這種情況下只能用線性掃描的方法，算法返回結(jié)果應(yīng)該是 7。
有的讀者也許會(huì)有這種想法：二分查找排除樓層的速度無疑是最快的，那干脆先用二分查找，等到只剩 1 個(gè)雞蛋的時(shí)候再執(zhí)行線性掃描，這樣得到的結(jié)果是不是就是最少的扔雞蛋次數(shù)呢？
很遺憾，并不是，比如說把樓層變高一些，100 層，給你 2 個(gè)雞蛋，你在 50 層扔一下，碎了，那就只能線性掃描 1～49 層了，最壞情況下要扔 50 次。
如果不要「二分」，變成「五分」「十分」都會(huì)大幅減少最壞情況下的嘗試次數(shù)。比方說第一個(gè)雞蛋每隔十層樓扔，在哪里碎了第二個(gè)雞蛋一個(gè)個(gè)線性掃描，總共不會(huì)超過 20 次?。
最優(yōu)解其實(shí)是 14 次。最優(yōu)策略非常多，而且并沒有什么規(guī)律可言。
說了這么多廢話，就是確保大家理解了題目的意思，而且認(rèn)識(shí)到這個(gè)題目確實(shí)復(fù)雜，就連我們手算都不容易，如何用算法解決呢？
二、思路分析
對動(dòng)態(tài)規(guī)劃問題，直接套我們以前多次強(qiáng)調(diào)的框架即可：這個(gè)問題有什么「狀態(tài)」，有什么「選擇」，然后窮舉。
「狀態(tài)」很明顯，就是當(dāng)前擁有的雞蛋數(shù) K 和需要測試的樓層數(shù) N。隨著測試的進(jìn)行，雞蛋個(gè)數(shù)可能減少，樓層的搜索范圍會(huì)減小，這就是狀態(tài)的變化。
「選擇」其實(shí)就是去選擇哪層樓扔雞蛋?；仡檮偛诺木€性掃描和二分思路，二分查找每次選擇到樓層區(qū)間的中間去扔雞蛋，而線性掃描選擇一層層向上測試。不同的選擇會(huì)造成狀態(tài)的轉(zhuǎn)移。
現(xiàn)在明確了「狀態(tài)」和「選擇」，動(dòng)態(tài)規(guī)劃的基本思路就形成了：肯定是個(gè)二維的 dp 數(shù)組或者帶有兩個(gè)狀態(tài)參數(shù)的 dp 函數(shù)來表示狀態(tài)轉(zhuǎn)移；外加一個(gè) for 循環(huán)來遍歷所有選擇，擇最優(yōu)的選擇更新狀態(tài)：
# 當(dāng)前狀態(tài)為 K 個(gè)雞蛋，面對 N 層樓
# 返回這個(gè)狀態(tài)下的最優(yōu)結(jié)果
def dp(K, N):
int res
for 1 <= i <= N:
res = min(res, 這次在第 i 層樓扔雞蛋)
return res
這段偽碼還沒有展示遞歸和狀態(tài)轉(zhuǎn)移，不過大致的算法框架已經(jīng)完成了。
我們選擇在第 i 層樓扔了雞蛋之后，可能出現(xiàn)兩種情況：雞蛋碎了，雞蛋沒碎。注意，這時(shí)候狀態(tài)轉(zhuǎn)移就來了：
如果雞蛋碎了，那么雞蛋的個(gè)數(shù) K 應(yīng)該減一，搜索的樓層區(qū)間應(yīng)該從 [1..N] 變?yōu)?[1..i-1] 共 i-1 層樓；
如果雞蛋沒碎，那么雞蛋的個(gè)數(shù) K 不變，搜索的樓層區(qū)間應(yīng)該從 [1..N] 變?yōu)?[i+1..N] 共 N-i 層樓。
PS：細(xì)心的讀者可能會(huì)問，在第i層樓扔雞蛋如果沒碎，樓層的搜索區(qū)間縮小至上面的樓層，是不是應(yīng)該包含第i層樓呀？不必，因?yàn)橐呀?jīng)包含了。開頭說了 F 是可以等于 0 的，向上遞歸后，第i層樓其實(shí)就相當(dāng)于第 0 層，可以被取到，所以說并沒有錯(cuò)誤。
因?yàn)槲覀円蟮氖?strong>最壞情況下扔雞蛋的次數(shù)，所以雞蛋在第 i 層樓碎沒碎，取決于那種情況的結(jié)果更大：
def dp(K, N):
for 1 <= i <= N:
# 最壞情況下的最少扔雞蛋次數(shù)
res = min(res,
max(
dp(K - 1, i - 1), # 碎
dp(K, N - i) # 沒碎
) + 1 # 在第 i 樓扔了一次
)
return res
遞歸的 base case 很容易理解：當(dāng)樓層數(shù) N 等于 0 時(shí)，顯然不需要扔雞蛋；當(dāng)雞蛋數(shù) K 為 1 時(shí)，顯然只能線性掃描所有樓層：
def dp(K, N):
if K == 1: return N
if N == 0: return 0
...
至此，其實(shí)這道題就解決了！只要添加一個(gè)備忘錄消除重疊子問題即可：
def superEggDrop(K: int, N: int):
memo = dict()
def dp(K, N) -> int:
# base case
if K == 1: return N
if N == 0: return 0
# 避免重復(fù)計(jì)算
if (K, N) in memo:
return memo[(K, N)]
res = float('INF')
# 窮舉所有可能的選擇
for i in range(1, N + 1):
res = min(res,
max(
dp(K, N - i),
dp(K - 1, i - 1)
) + 1
)
# 記入備忘錄
memo[(K, N)] = res
return res
return dp(K, N)
這個(gè)算法的時(shí)間復(fù)雜度是多少呢？動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度就是子問題個(gè)數(shù) × 函數(shù)本身的復(fù)雜度。
函數(shù)本身的復(fù)雜度就是忽略遞歸部分的復(fù)雜度，這里 dp 函數(shù)中有一個(gè) for 循環(huán)，所以函數(shù)本身的復(fù)雜度是 O(N)。
子問題個(gè)數(shù)也就是不同狀態(tài)組合的總數(shù)，顯然是兩個(gè)狀態(tài)的乘積，也就是 O(KN)。
所以算法的總時(shí)間復(fù)雜度是 O(K*N^2), 空間復(fù)雜度 O(KN)。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
三、疑難解答
這個(gè)問題很復(fù)雜，但是算法代碼卻十分簡潔，這就是動(dòng)態(tài)規(guī)劃的特性，窮舉加備忘錄/DP table 優(yōu)化，真的沒啥新意。
首先，有讀者可能不理解代碼中為什么用一個(gè) for 循環(huán)遍歷樓層 [1..N]，也許會(huì)把這個(gè)邏輯和之前探討的線性掃描混為一談。其實(shí)不是的，這只是在做一次「選擇」。
比方說你有 2 個(gè)雞蛋，面對 10 層樓，你這次選擇去哪一層樓扔呢？不知道，那就把這 10 層樓全試一遍。至于下次怎么選擇不用你操心，有正確的狀態(tài)轉(zhuǎn)移，遞歸會(huì)算出每個(gè)選擇的代價(jià)，我們?nèi)∽顑?yōu)的那個(gè)就是最優(yōu)解。
另外，這個(gè)問題還有更好的解法，比如修改代碼中的 for 循環(huán)為二分搜索，可以將時(shí)間復(fù)雜度降為 O(K*N*logN)；再改進(jìn)動(dòng)態(tài)規(guī)劃解法可以進(jìn)一步降為 O(KN)；使用數(shù)學(xué)方法解決，時(shí)間復(fù)雜度達(dá)到最優(yōu) O(K*logN)，空間復(fù)雜度達(dá)到 O(1)。
二分的解法也有點(diǎn)誤導(dǎo)性，你很可能以為它跟我們之前討論的二分思路扔雞蛋有關(guān)系，實(shí)際上沒有半毛錢關(guān)系。能用二分搜索是因?yàn)闋顟B(tài)轉(zhuǎn)移方程的函數(shù)圖像具有單調(diào)性，可以快速找到最值。
二分搜索的優(yōu)化思路也許是我們可以盡力嘗試寫出的，而修改狀態(tài)轉(zhuǎn)移的解法可能是不容易想到的，可以借此見識(shí)一下動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)的玄妙，當(dāng)做思維拓展。
二分搜索優(yōu)化
之前提到過這個(gè)解法，核心是因?yàn)闋顟B(tài)轉(zhuǎn)移方程的單調(diào)性，這里可以具體展開看看。
首先簡述一下原始動(dòng)態(tài)規(guī)劃的思路：
1、暴力窮舉嘗試在所有樓層 1 <= i <= N 扔雞蛋，每次選擇嘗試次數(shù)最少的那一層；
2、每次扔雞蛋有兩種可能，要么碎，要么沒碎；
3、如果雞蛋碎了，F 應(yīng)該在第 i 層下面，否則，F 應(yīng)該在第 i 層上面；
4、雞蛋是碎了還是沒碎，取決于哪種情況下嘗試次數(shù)更多，因?yàn)槲覀兿肭蟮氖亲顗那闆r下的結(jié)果。
核心的狀態(tài)轉(zhuǎn)移代碼是這段：
# 當(dāng)前狀態(tài)為 K 個(gè)雞蛋，面對 N 層樓
# 返回這個(gè)狀態(tài)下的最優(yōu)結(jié)果
def dp(K, N):
for 1 <= i <= N:
# 最壞情況下的最少扔雞蛋次數(shù)
res = min(res,
max(
dp(K - 1, i - 1), # 碎
dp(K, N - i) # 沒碎
) + 1 # 在第 i 樓扔了一次
)
return res
這個(gè) for 循環(huán)就是下面這個(gè)狀態(tài)轉(zhuǎn)移方程的具體代碼實(shí)現(xiàn)：
如果能夠理解這個(gè)狀態(tài)轉(zhuǎn)移方程，那么就很容易理解二分查找的優(yōu)化思路。
首先我們根據(jù) dp(K, N) 數(shù)組的定義（有 K 個(gè)雞蛋面對 N 層樓，最少需要扔幾次），很容易知道 K 固定時(shí)，這個(gè)函數(shù)隨著 N 的增加一定是單調(diào)遞增的，無論你策略多聰明，樓層增加測試次數(shù)一定要增加。
那么注意 dp(K - 1, i - 1) 和 dp(K, N - i) 這兩個(gè)函數(shù)，其中 i 是從 1 到 N 單增的，如果我們固定 K 和 N，把這兩個(gè)函數(shù)看做關(guān)于 i 的函數(shù)，前者隨著 i 的增加應(yīng)該也是單調(diào)遞增的，而后者隨著 i 的增加應(yīng)該是單調(diào)遞減的：
這時(shí)候求二者的較大值，再求這些最大值之中的最小值，其實(shí)就是求這兩條直線交點(diǎn)，也就是紅色折線的最低點(diǎn)嘛。
我們前文「二分查找只能用來查找元素嗎」講過，二分查找的運(yùn)用很廣泛，形如下面這種形式的 for 循環(huán)代碼：
for (int i = 0; i < n; i++) {
if (isOK(i))
return i;
}
都很有可能可以運(yùn)用二分查找來優(yōu)化線性搜索的復(fù)雜度，回顧這兩個(gè) dp 函數(shù)的曲線，我們要找的最低點(diǎn)其實(shí)就是這種情況：
for (int i = 1; i <= N; i++) {
if (dp(K - 1, i - 1) == dp(K, N - i))
return dp(K, N - i);
}
熟悉二分搜索的同學(xué)肯定敏感地想到了，這不就是相當(dāng)于求 Valley（山谷）值嘛，可以用二分查找來快速尋找這個(gè)點(diǎn)的，直接看代碼吧，整體的思路還是一樣，只是加快了搜索速度：
def superEggDrop(self, K: int, N: int) -> int:
memo = dict()
def dp(K, N):
if K == 1: return N
if N == 0: return 0
if (K, N) in memo:
return memo[(K, N)]
# for 1 <= i <= N:
# res = min(res,
# max(
# dp(K - 1, i - 1),
# dp(K, N - i)
# ) + 1
# )
res = float('INF')
# 用二分搜索代替線性搜索
lo, hi = 1, N
while lo <= hi:
mid = (lo + hi) // 2
broken = dp(K - 1, mid - 1) # 碎
not_broken = dp(K, N - mid) # 沒碎
# res = min(max(碎，沒碎) + 1)
if broken > not_broken:
hi = mid - 1
res = min(res, broken + 1)
else:
lo = mid + 1
res = min(res, not_broken + 1)
memo[(K, N)] = res
return res
return dp(K, N)
這個(gè)算法的時(shí)間復(fù)雜度是多少呢？動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度就是子問題個(gè)數(shù) × 函數(shù)本身的復(fù)雜度。
函數(shù)本身的復(fù)雜度就是忽略遞歸部分的復(fù)雜度，這里 dp 函數(shù)中用了一個(gè)二分搜索，所以函數(shù)本身的復(fù)雜度是 O(logN)。
子問題個(gè)數(shù)也就是不同狀態(tài)組合的總數(shù)，顯然是兩個(gè)狀態(tài)的乘積，也就是 O(KN)。
所以算法的總時(shí)間復(fù)雜度是 O(K*N*logN), 空間復(fù)雜度 O(KN)。效率上比之前的算法 O(KN^2) 要高效一些。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
重新定義狀態(tài)轉(zhuǎn)移
前文「不同定義有不同解法」就提過，找動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移本就是見仁見智，比較玄學(xué)的事情，不同的狀態(tài)定義可以衍生出不同的解法，其解法和復(fù)雜程度都可能有巨大差異。這里就是一個(gè)很好的例子。
再回顧一下我們之前定義的 dp 數(shù)組含義：
def dp(k, n) -> int
# 當(dāng)前狀態(tài)為 k 個(gè)雞蛋，面對 n 層樓
# 返回這個(gè)狀態(tài)下最少的扔雞蛋次數(shù)
用 dp 數(shù)組表示的話也是一樣的：
dp[k][n] = m
# 當(dāng)前狀態(tài)為 k 個(gè)雞蛋，面對 n 層樓
# 這個(gè)狀態(tài)下最少的扔雞蛋次數(shù)為 m
按照這個(gè)定義，就是確定當(dāng)前的雞蛋個(gè)數(shù)和面對的樓層數(shù)，就知道最小扔雞蛋次數(shù)。最終我們想要的答案就是 dp(K, N) 的結(jié)果。
這種思路下，肯定要窮舉所有可能的扔法的，用二分搜索優(yōu)化也只是做了「剪枝」，減小了搜索空間，但本質(zhì)思路沒有變，還是窮舉。
現(xiàn)在，我們稍微修改 dp 數(shù)組的定義，確定當(dāng)前的雞蛋個(gè)數(shù)和最多允許的扔雞蛋次數(shù)，就知道能夠確定 F 的最高樓層數(shù)。具體來說是這個(gè)意思：
dp[k][m] = n
# 當(dāng)前有 k 個(gè)雞蛋，可以嘗試扔 m 次雞蛋
# 這個(gè)狀態(tài)下，最壞情況下最多能確切測試一棟 n 層的樓
# 比如說 dp[1][7] = 7 表示：
# 現(xiàn)在有 1 個(gè)雞蛋，允許你扔 7 次;
# 這個(gè)狀態(tài)下最多給你 7 層樓，
# 使得你可以確定樓層 F 使得雞蛋恰好摔不碎
# （一層一層線性探查嘛）
這其實(shí)就是我們原始思路的一個(gè)「反向」版本，我們先不管這種思路的狀態(tài)轉(zhuǎn)移怎么寫，先來思考一下這種定義之下，最終想求的答案是什么？
我們最終要求的其實(shí)是扔雞蛋次數(shù) m，但是這時(shí)候 m 在狀態(tài)之中而不是 dp 數(shù)組的結(jié)果，可以這樣處理：
int superEggDrop(int K, int N) {
int m = 0;
while (dp[K][m] < N) {
m++;
// 狀態(tài)轉(zhuǎn)移...
}
return m;
}
題目不是給你 K 雞蛋，N 層樓，讓你求最壞情況下最少的測試次數(shù) m 嗎？while 循環(huán)結(jié)束的條件是 dp[K][m] == N，也就是給你 K 個(gè)雞蛋，測試 m 次，最壞情況下最多能測試 N 層樓。
注意看這兩段描述，是完全一樣的！所以說這樣組織代碼是正確的，關(guān)鍵就是狀態(tài)轉(zhuǎn)移方程怎么找呢？還得從我們原始的思路開始講。之前的解法配了這樣圖幫助大家理解狀態(tài)轉(zhuǎn)移思路：
這個(gè)圖描述的僅僅是某一個(gè)樓層 i，原始解法還得線性或者二分掃描所有樓層，要求最大值、最小值。但是現(xiàn)在這種 dp 定義根本不需要這些了，基于下面兩個(gè)事實(shí)：
1、無論你在哪層樓扔雞蛋，雞蛋只可能摔碎或者沒摔碎，碎了的話就測樓下，沒碎的話就測樓上。
2、無論你上樓還是下樓，總的樓層數(shù) = 樓上的樓層數(shù) + 樓下的樓層數(shù) + 1（當(dāng)前這層樓）。
根據(jù)這個(gè)特點(diǎn)，可以寫出下面的狀態(tài)轉(zhuǎn)移方程：
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1
dp[k][m - 1] 就是樓上的樓層數(shù)，因?yàn)殡u蛋個(gè)數(shù) k 不變，也就是雞蛋沒碎，扔雞蛋次數(shù) m 減一；
dp[k - 1][m - 1] 就是樓下的樓層數(shù)，因?yàn)殡u蛋個(gè)數(shù) k 減一，也就是雞蛋碎了，同時(shí)扔雞蛋次數(shù) m 減一。
PS：這個(gè) m 為什么要減一而不是加一？之前定義得很清楚，這個(gè) m 是一個(gè)允許的次數(shù)上界，而不是扔了幾次。
至此，整個(gè)思路就完成了，只要把狀態(tài)轉(zhuǎn)移方程填進(jìn)框架即可：
int superEggDrop(int K, int N) {
// m 最多不會(huì)超過 N 次（線性掃描）
int[][] dp = new int[K + 1][N + 1];
// base case:
// dp[0][..] = 0
// dp[..][0] = 0
// Java 默認(rèn)初始化數(shù)組都為 0
int m = 0;
while (dp[K][m] < N) {
m++;
for (int k = 1; k <= K; k++)
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
}
return m;
}
如果你還覺得這段代碼有點(diǎn)難以理解，其實(shí)它就等同于這樣寫：
for (int m = 1; dp[K][m] < N; m++)
for (int k = 1; k <= K; k++)
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
看到這種代碼形式就熟悉多了吧，因?yàn)槲覀円蟮牟皇?dp 數(shù)組里的值，而是某個(gè)符合條件的索引 m，所以用 while 循環(huán)來找到這個(gè) m 而已。
這個(gè)算法的時(shí)間復(fù)雜度是多少？很明顯就是兩個(gè)嵌套循環(huán)的復(fù)雜度 O(KN)。
另外注意到 dp[m][k] 轉(zhuǎn)移只和左邊和左上的兩個(gè)狀態(tài)有關(guān)，所以很容易優(yōu)化成一維 dp 數(shù)組，這里就不寫了。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
還可以再優(yōu)化
再往下就要用一些數(shù)學(xué)方法了，不具體展開，就簡單提一下思路吧。
在剛才的思路之上，注意函數(shù) dp(m, k) 是隨著 m 單增的，因?yàn)殡u蛋個(gè)數(shù) k 不變時(shí)，允許的測試次數(shù)越多，可測試的樓層就越高。
這里又可以借助二分搜索算法快速逼近 dp[K][m] == N 這個(gè)終止條件，時(shí)間復(fù)雜度進(jìn)一步下降為 O(KlogN)，我們可以設(shè) g(k, m) =……
算了算了，打住吧。我覺得我們能夠?qū)懗?O(K*N*logN) 的二分優(yōu)化算法就行了，后面的這些解法呢，聽個(gè)響鼓個(gè)掌就行了，把欲望限制在能力的范圍之內(nèi)才能擁有快樂！
不過可以肯定的是，根據(jù)二分搜索代替線性掃描 m 的取值，代碼的大致框架肯定是修改窮舉 m 的 for 循環(huán)：
// 把線性搜索改成二分搜索
// for (int m = 1; dp[K][m] < N; m++)
int lo = 1, hi = N;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (... < N) {
lo = ...
} else {
hi = ...
}
for (int k = 1; k <= K; k++)
// 狀態(tài)轉(zhuǎn)移方程
}
簡單總結(jié)一下吧，第一個(gè)二分優(yōu)化是利用了 dp 函數(shù)的單調(diào)性，用二分查找技巧快速搜索答案；第二種優(yōu)化是巧妙地修改了狀態(tài)轉(zhuǎn)移方程，簡化了求解了流程，但相應(yīng)的，解題邏輯比較難以想到；后續(xù)還可以用一些數(shù)學(xué)方法和二分搜索進(jìn)一步優(yōu)化第二種解法，不過看了看鏡子中的發(fā)量，算了。
本文終，希望對你有一點(diǎn)啟發(fā)。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星！
