在網(wǎng)上查資料的時候無意間看到了這道谷歌面試題，據(jù)說這道面試題刷了好多的大牛(可怕)杉武。讀了幾篇文章，讀懂以后感覺這種解決問題的思路和方法實在是太巧妙了艺智，佩服！在最壞的情況下仍要保證付出最小的代價封拧，這種思想非常值得讓人去學習和借鑒泽西，所以寫一篇博客記錄一下自己對這道題的理解。
題目
一幢 200 層的大樓捧杉，給你兩個雞蛋味抖，如果在第 n 層扔下雞蛋仔涩，雞蛋不碎粘舟，那么從第 n-1 層扔雞蛋，都不碎霞揉。這兩只雞蛋一模一樣，不碎的話可以扔無數(shù)次适秩，且雞蛋在0層不會碎秽荞。設計一種策略能保證可以測出雞蛋恰好會碎的樓層岗宣，且如果該策略是最壞的情況所扔次數(shù)最少蚂会。
解決問題
思維分析
首先我們需要確定最壞情況是什么樣子的。
假設n是我們的決定第一次嘗試的樓層耗式，第一個雞蛋從n層開始扔胁住。
- 如果沒有壞趁猴，那么我們就可以從[n+1,100]這個區(qū)間扔雞蛋了，這個時候怎么扔就是我們需要考慮的策略彪见。
- 但是如果運氣比較背儡司，雞蛋壞了_!那么這個時候我們就只有一個雞蛋了，所以為了滿足我們要測出恰好會碎的樓層余指，我們只能從1樓一直扔到n-1樓捕犬。這個時候我們的最壞情況就是n次。
雞蛋沒有壞該怎么選擇第二次以及以后扔雞蛋的策略呢酵镜？
由于沒有碎碉碉，所以第n層對于我們而言和第0層是一樣一樣的，所以我們不能采用一層一層增加的方式扔雞蛋淮韭！因為有兩個雞蛋靠粪，比較任性昔善。下面提出幾個合理的假設，然后分析：
- 增加n層：碎了的話袖订，最壞情況就是我們還要扔2n-n-1+2=n+1次，這個時候最壞情況比第一次還壞，而且照這個趨勢下去龄广，最壞情況只會越來越壞，是不可控的敲才，所以這種策略拋棄剃氧。
- 增加大于n層：和增加n層一樣，如果第一個雞蛋碎了那最壞情況就是越來越壞，且比增加n層更壞（可以自己做個簡單的算術推導一下）畦幢。
- 增加小于n層：隨著n的不斷減小，最壞情況下需要仍的次數(shù)恒定為n是不會變的（因為第一次就碎了吗氏，對于這種情況就是最壞情況）。那么我們需要考慮的是如何使扔的次數(shù)最少，想想看仿村，果斷取n-1，這樣既保證了快速找到剛好碎的樓層畏鼓，又保證了最壞情況扔的次數(shù)最少。
- 所以我們最后的策略是增加n-1層贵少。
以上就是一個分析過程滔灶，對于第三次，第四次....都可以遞歸的進行分析。
由于最好情況是第一個雞蛋一直扔到了100層表箭，而100層與n之間是有一個函數(shù)關系的崔拥，下面就可以列出一個等式：
n+(n-1)+(n-2)+...+1=100=n(n+1)/2
所以n約等于14
所以第一次從第十四層開始扔拆魏，最壞情況就是第一次就碎了贴膘，然后需要從1樓開始一層一層的扔垢揩，共扔14次。
編程解答
以上是分析然后數(shù)學解答，還有一種代碼做法撮奏，這里我就直接引用知乎大神的代碼了哈。
設f(n, m)為n層樓, m個蛋所需次數(shù), 那么它就成了一道DP題
import functools
def f(n, m):
if n == 0:
return 0
if m == 1:
return n
ans = min([max([f(i - 1, m - 1), f(n - i, m)]) for i in range(1, n + 1)]) + 1
return ans
print(f(100, 2))
print(f(200, 2))
