本來看算法4看得好好的，結果有一個作業提到了這個雞蛋掉落問題，實在是想不通啊otz。
搜索後發現是leetcode上的一道經典面試題~因為過於經典，已經被踢出google面試題庫了(。）
那我們就直接看看leetcode上的題目叭！
leetcode現在有中文站，看起來更方便了：https://leetcode-cn.com/problems/super-egg-drop/solution/
--
你將獲得 K 個雞蛋，並可以使用一棟從 1 到 N 共有 N 層樓的建築。
每個蛋的功能都是一樣的，如果一個蛋碎了，你就不能再把它掉下去。
你知道存在樓層 F ，滿足 0 <= F <= N 任何從高於 F 的樓層落下的雞蛋都會碎，從 F 樓層或比它低的樓層落下的雞蛋都不會破。
每次移動，你可以取一個雞蛋（如果你有完整的雞蛋）並把它從任一樓層 X 扔下（滿足 1 <= X <= N）。
你的目標是確切地知道 F 的值是多少。
無論 F 的初始值如何，你確定 F 的值的最小移動次數是多少？
--
看題目第一反應就是"二分查找"。
但是細想就覺得不對。
舉個慄子：
如果有2顆蛋，100層樓。
用二分法，第一次從50層扔，蛋碎了。第二次從25層扔，蛋又碎了。
蛋碎光了，我們無法知道F是第幾層了。
雞蛋碎了就減少了一次機會，這點特別重要！！
手上只有一個雞蛋的時候，只能從第一層，一層層的爬樓扔，才能知道F層。如果F是49層，總共就要扔50次?
50次也太多了，這種算法題肯定有更少次數的方法_(:з」∠)_
---
咋樣才能確定F層呢?
1.<=F層的不會破
2.>F層的會破
只有找到了破與不破的邊界，才能找到F層~那就倒著想~
比如一共扔了x次才找到了F層。
扔第x次和第n（1<=n<x-1）次的時候，分別是在F層和F+1層扔的（順序可以打亂）~
兩次扔雞蛋的層數相鄰，才能找到F層嘛。
由此可知，測出F層的方法和雞蛋數、扔的次數、在哪一層扔的都有關。
在儘可能少的雞蛋和儘可能少的次數前提下，咋確定F層捏?
如果我們是歐皇，就說明我們第一次扔到了F層~可以少走很多彎路~一顆蛋+2次就能確認F層：
第一次湊巧扔在了F層，沒碎。
第二次因為只有一顆蛋，怕的一批，只敢先扔在了F+1層，碎了。
第一次扔的樓層就是F層。問題結束。
但我們不是歐皇。
非酋的我們，只能考慮在所有情況下，怎麼扔才能次數最少的確認F層？
F層的值在雞蛋數和樓層數固定的情況下是可變的，所以不能用：
K個雞蛋在N樓中求出F層
「fun(雞蛋數K，樓層數N)=F層的值」
來解題。
但在雞蛋數和樓層數固定的情況下，確定F層用的最小次數是恆定的！
這就是這題的真實問題~
於是問題解析為：
K個雞蛋在[1, N]層中最少扔多少次才能求出F層
「fun(雞蛋數K，樓層數N)=測出F層的最少扔的次數」
題目終於理解清白了，開始正式做題~
不知道咋搞的時候，就設置一個未知數想想~
按照直觀思路，一次次的拋雞蛋試試~
前提：K個雞蛋，N層樓，K個雞蛋在[1, N]層中最少扔t次才能求出F層
問題：求t
我們在x層丟了第一個雞蛋，有兩種後果：
蛋碎了，我們還有K-1個雞蛋，問題變為K-1個蛋在[1, x-1]層中最少扔n1次才能求出F層；
蛋沒碎，我們還有K個雞蛋，問題變為K個蛋在[x+1, N]層中最少扔n2次才能求出F層。
找到n1和n2中最大的數字：max(n1, n2)，再加上第一次扔的次數1，即為t。
fun(雞蛋數K，樓層數N) = 1 + max(n1, n2)
又因為：
n1 = fun(雞蛋數K-1，樓層數x-1)
n2 = fun(雞蛋數K，樓層數N-x)
轉換為：
fun(雞蛋數K，樓層數N) = 1 + max(fun(雞蛋數K-1，樓層數x-1), fun(雞蛋數K，樓層數N-x))
哎呀，這不是遞歸嗎~
一個大問題拆分為了一個個小問題~
from functools import lru_cache
class RecursionSuperEgg(object): '''遞歸方法求雞蛋掉落問題''' @lru_cache(maxsize=None) def superEggDrop(self, egg: int, floor: int) -> int: if egg == 0: min_times = 0 elif egg == 1: min_times = floor elif floor == 0: min_times = 0 else: min_times_list = list() for current_floor in range(1, floor + 1): one_min_times = 1 + max(self.superEggDrop(egg - 1, current_floor - 1), self.superEggDrop(egg, floor - current_floor)) min_times_list.append(one_min_times) min_times = min(min_times_list)
return min_times
if __name__ == "__main__": recursion_super_egg = RecursionSuperEgg() print(recursion_super_egg.superEggDrop(2, 100))問題解決啦~
2蛋100樓，最多丟14次就能得出F層~
----
但是這種遍歷每一層樓的遞歸太佔資源了，leetcode不讓我們這樣搞。
我們得想想幾個辦法：
還是用遞歸，想辦法不遍歷每一層樓，也能求出最小次數
不用遞歸，用船新的方法~
---
先來看看遞歸能不能改善：
之前的for循環是這樣寫的：
for current_floor in range(1, floor + 1): one_min_times = 1 + max(self.superEggDrop(egg - 1, current_floor - 1), self.superEggDrop(egg, floor - current_floor))1<=current_floor<=floor
可以用二分法~
先讓current_floor取int((1+floor)/2)（這裡隨便向上or向下取整）；
比較碎了和沒碎兩種情況中，哪一種的次數多：
2.1如果碎了的最多次數是n1：
for current_floor in range(1, int((1+floor)/2)):2.2如果沒碎的最多次數是n2：
for current_floor in range(int((1+floor)/2), floor):比較這兩者中次數最多的，就是此雞蛋數+此樓層數在int((1+floor)/2)層時的最多次數啦~：
fun(雞蛋數K，樓層數N) = 1 + max(n1, n2)
就這樣一次次二分查找，就能把遍歷範圍從[1, floor]的floor個變為：
floor/2個
floor/4個
直到個數變為2個，就不能再用二分查找了，但是這時候也把floor次的遍歷次數減少了很多很多了~
比如100層樓~，正常需要遍歷100遍~
二分查找的話，最多只用遍歷6遍~:
50 25 13 6 3 1
大大減少了調用遞歸函數的次數！
代碼搞起來~
class Solution(object): @lru_cache(maxsize=None) def superEggDrop(self, K: int, N: int) -> int: memo = {} def dp(k, n): if (k, n) not in memo: if n == 0: ans = 0 elif k == 1: ans = n else: lo, hi = 1, n while lo + 1 < hi: x = (lo + hi) // 2 t1 = dp(k-1, x-1) t2 = dp(k, n-x)
if t1 < t2: lo = x elif t1 > t2: hi = x else: lo = hi = x print(lo, hi) ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x)) for x in (lo, hi))
memo[(k, n)] = ans return memo[k, n]
return dp(K, N)---
其實題在這裡就結束啦~
但是還有個有趣的規律，有興趣的可以繼續看看~
我們用枚舉法記錄一下2顆蛋100層的情況，第一次選擇第1層，第2層，第3層....第100層扔蛋的最小次數~
class Solution_time_limit_exceeded(object): ''' Time Limit Exceeded ''' def superEggDrop(self, egg: int, floor: int) -> int: self.first_floor_times_dict = dict()
cache_egg_and_floor = [[0]*(egg+1) for floor in range(floor+1)]
def each_min_times(egg, floor): if egg == 0: return 0 elif egg == 1: return floor
if floor == 0: return 0 elif floor == 1: return 1
if not cache_egg_and_floor[floor][egg]: all_floor_max_times_list = list() for one_floor in range(1, floor+1): max_times = max(each_min_times(egg-1, one_floor-1), each_min_times(egg, floor-one_floor)) + 1 all_floor_max_times_list.append(max_times) self.first_floor_times_dict[one_floor] = max_times
all_min_times = min(all_floor_max_times_list) if all_min_times >= floor: all_min_times = floor
cache_egg_and_floor[floor][egg] = all_min_times
return cache_egg_and_floor[floor][egg]
return each_min_times(egg, floor)
def run(self): self.superEggDrop(2, 100) print(self.first_floor_times_dict)答案是:
{1: 15, 2: 15, 3: 15, 4: 15, 5: 15, 6: 15, 7: 15, 8: 15, 9: 14, 10: 14, 11: 14, 12: 14, 13: 14, 14: 14, 15: 15, 16: 16, 17: 17, 18: 18, 19: 19, 20: 20, 21: 21, 22: 22, 23: 23, 24: 24, 25: 25, 26: 26, 27: 27, 28: 28, 29: 29, 30: 30, 31: 31, 32: 32, 33: 33, 34: 34, 35: 35, 36: 36, 37: 37, 38: 38, 39: 39, 40: 40, 41: 41, 42: 42, 43: 43, 44: 44, 45: 45, 46: 46, 47: 47, 48: 48, 49: 49, 50: 50, 51: 51, 52: 52, 53: 53, 54: 54, 55: 55, 56: 56, 57: 57, 58: 58, 59: 59, 60: 60, 61: 61, 62: 62, 63: 63, 64: 64, 65: 65, 66: 66, 67: 67, 68: 68, 69: 69, 70: 70, 71: 71, 72: 72, 73: 73, 74: 74, 75: 75, 76: 76, 77: 77, 78: 78, 79: 79, 80: 80, 81: 81, 82: 82, 83: 83, 84: 84, 85: 85, 86: 86, 87: 87, 88: 88, 89: 89, 90: 90, 91: 91, 92: 92, 93: 93, 94: 94, 95: 95, 96: 96, 97: 97, 98: 98, 99: 99, 100: 100}
第一次在第1層扔時，最小次數為15
第一次在第2層扔時，最小次數為15
...
第一次在第9層扔時，最小次數為14
...
第一次在第14層扔時，最小次數為14
第一次在第15層扔時，最小次數為15
...
可以觀察到，從9-14層扔下去，最小次數都是14~也是這題的答案~
那麼是不是總有個臨界值，第一次在第x層扔時，最小次數為x，同時這個x層也是F層？
因為從第一次從第1層~第N層，最小次數是先減少後增加的，所以一定會有：
第一次在第x層扔時，最小次數為x，同時這個x層也是F層
這種情況出現!
題目再次轉換為：
求出最小次數，就等於求出了F的值~
class RecursionSuperEgg(object): @lru_cache(maxsize=None) def superEggDrop(self, egg: int, floor: int) -> int: if egg == 0: min_times = 0 elif egg == 1: min_times = floor elif floor == 0: min_times = 0 else: min_times_list = list() for current_floor in range(1, floor + 1): one_min_times = 1 + max(self.superEggDrop(egg - 1, current_floor - 1), self.superEggDrop(egg, floor - current_floor)) min_times_list.append(one_min_times) min_times = min(min_times_list)
return min_times好了，這題真的做完啦~
是不是很赤幾~