之前被某小哥以智商測(cè)試題一般的考過(guò)一道題：
100層樓表箭，球可能會(huì)在某一層樓摔碎幸撕，問(wèn)用2個(gè)球笛粘，最壞情況下幾次測(cè)試可以找出該樓層？
以哥們這種博聞強(qiáng)識(shí)的腦子队腐，當(dāng)時(shí)就給出了答案：14。
某小哥不以為意奏篙，微微一笑：“怎么算出來(lái)的柴淘？”
思考半天未果，只好老老實(shí)實(shí)的交代：”之前從百度上看到的秘通，好像是個(gè)谷歌的面試題为严，我回去好好學(xué)習(xí)學(xué)習(xí)再出來(lái)跟你裝逼……“
于是便引出了這篇關(guān)于動(dòng)態(tài)規(guī)劃的思考肺稀。
先上倆動(dòng)態(tài)規(guī)劃的百科鏈接第股，以供大家觀賞(根據(jù)自己的逼格自行挑選)：
我再稍微跟大家嘮一嘮啥叫動(dòng)態(tài)規(guī)劃，說(shuō)白了就是——如何把一件聽上去就很煩人的事话原，分解成一件件不是那么煩人的事夕吻。
這么一說(shuō)，是不是突然就有種茅塞頓開的感覺繁仁？涉馅！臥槽？好像什么都能適用盎剖稚矿？然而并不是……想搞動(dòng)態(tài)規(guī)劃，還需要滿足下面2個(gè)條件才行捻浦。
1.具有最優(yōu)子結(jié)構(gòu)晤揣。即無(wú)論過(guò)去未來(lái)如何變化，將最優(yōu)子結(jié)構(gòu)得出的解朱灿，永遠(yuǎn)都是每一個(gè)子結(jié)構(gòu)里的最優(yōu)解昧识。
2.無(wú)后效性。這個(gè)名字聽上去可能有點(diǎn)兒懵母剥，那咱們看看它的定義：每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)滞诺。驚不驚喜？是不是更懵了环疼？emmmm……我一開始也挺懵习霹，簡(jiǎn)單點(diǎn)兒說(shuō)，就是”一個(gè)事情炫隶，可以被劃分階段淋叶，劃分階段后，未來(lái)的事情伪阶，不再受之前狀態(tài)的影響“煞檩，舉個(gè)反例吧：玩游戲棋的時(shí)候处嫌，突然加了個(gè)規(guī)矩，不能走重復(fù)的格子斟湃，這也就意味著熏迹，你每一步的動(dòng)作，都會(huì)影響到未來(lái)的動(dòng)作凝赛。整件事情注暗，是無(wú)法被劃分階段的。因?yàn)楫?dāng)你走過(guò)了這一步墓猎，未來(lái)就不能走這一步了捆昏。未來(lái)永遠(yuǎn)會(huì)受到影響。
大概清楚了么毙沾？動(dòng)態(tài)規(guī)劃的兩個(gè)要求骗卜，下面還是回歸到這道題上來(lái)。
先捋一捋思路左胞。咱先忘了剛才說(shuō)的這些邏輯概念啥的寇仓，從一個(gè)小懵逼開始捋思路。
2個(gè)球罩句，測(cè)臨界點(diǎn)焚刺。咋測(cè)？
先說(shuō)最笨的方法吧——一層一層的來(lái)门烂。反正我從底測(cè)到頂乳愉，哪層摔碎了哪層就是臨界值。
這也就是大家最喜歡的方法屯远，暴力窮舉（我知道蔓姚，我又懂你了）
暴力窮舉是人類進(jìn)步的階梯——魯迅
當(dāng)然，如果只有一個(gè)球慨丐，咱們也只有這一種辦法坡脐，因?yàn)椋に榱司蜎](méi)球了房揭。
所以說(shuō)备闲，這道題妙就妙在這里了，他給了兩個(gè)球捅暴！
兩個(gè)球恬砂！題目作者想向我們表達(dá)什么呢？
每個(gè)男人都應(yīng)該有兩個(gè)球蓬痒！少一個(gè)都是不健全泻骤！
這是在給我們?cè)囧e(cuò)的機(jī)會(huì)啊！有了試錯(cuò)狱掂，是不是問(wèn)題一下就好解決多了演痒？
50樓一扔，碎了往下面找趋惨，沒(méi)碎往上面找鸟顺。
這是啥？同學(xué)們器虾！二分法罢锘Α！
是不是一下子就覺得曾撤，蹭蹭蹭蹭蹭，速度瞬間就上來(lái)了晕粪！50樓沒(méi)碎挤悉，75樓接著摔，再?zèng)]碎87樓……反之50樓碎了巫湘，25樓接著摔装悲，要是25樓再碎了……再碎了……再碎了好像就沒(méi)球了……
沒(méi)球了豈不是完蛋了！所以如果50樓碎了尚氛，下一個(gè)球诀诊，就只能從1樓開始扔，一直扔到50層阅嘶。二分法這時(shí)也陷入了瓶頸属瓣。最壞的情況下，需要測(cè)50次讯柔。
那還有沒(méi)有更簡(jiǎn)單的辦法呢抡蛙？
啥？不知道魂迄？我開頭絮叨了那么一堆粗截，你跟我說(shuō)你不知道？捣炬！
認(rèn)真讀題同樣是人類進(jìn)步的階梯——魯迅
是的熊昌，動(dòng)態(tài)規(guī)劃，老帶勁了湿酸！
要用動(dòng)態(tài)規(guī)劃婿屹，咱們就先套一套，這個(gè)東西能不能用動(dòng)態(tài)規(guī)劃來(lái)做稿械。
首先第一點(diǎn)选泻，無(wú)后效性，要知道一個(gè)有后效性的事件是無(wú)法用動(dòng)態(tài)規(guī)劃去解決的，那么看看這個(gè)事件页眯，是否符合呢梯捕？我們一步步來(lái)，先分階段窝撵，我們可以把每一次扔球分成一個(gè)階段傀顾，而每一次扔球的結(jié)果，都是對(duì)當(dāng)前階段的一個(gè)總結(jié)碌奉，即——每次結(jié)果短曾，都會(huì)告訴我，當(dāng)前樓層會(huì)不會(huì)把球摔碎赐劣。當(dāng)你下次再扔球的時(shí)候嫉拐，無(wú)論高低或在同樓層扔，都不會(huì)受到本次結(jié)果的影響魁兼，那么我們可以斷定婉徘，這個(gè)事件，是一個(gè)無(wú)后效性的事件咐汞。
其次盖呼，具有最優(yōu)子結(jié)構(gòu)。首先從上面無(wú)后效性的判斷我們發(fā)現(xiàn)化撕，該事件具有子結(jié)構(gòu)是毋庸置疑的几晤，每次扔球，都是一個(gè)子結(jié)構(gòu)事件植阴，那么接下來(lái)蟹瘾，我們只需要去思考，如何找到最優(yōu)的子結(jié)構(gòu)事件就好了墙贱。
? ? 如何判斷最優(yōu)呢热芹？這時(shí)候就要從我們的需求入手了。我們需要找到最壞情況下最少需要的步數(shù)惨撇。也就是說(shuō)伊脓，咱們根本不用考慮最快的時(shí)候能有多快，只要保證無(wú)論這個(gè)樓層出現(xiàn)在哪魁衙，這個(gè)結(jié)果都還可以报腔，也就是，我們算法的穩(wěn)定性需要保證剖淀。聽上去有點(diǎn)兒繞纯蛾，不用著急，咱們可以先從結(jié)果反推纵隔。
????我們可以先思考這樣的一個(gè)問(wèn)題翻诉，我們有兩個(gè)球炮姨，明明一個(gè)球暴力窮舉就可以解決了，那么另一個(gè)球的作用是干什么的呢碰煌？這時(shí)大家腦子里肯定瞬間就萌生出一個(gè)想法舒岸，鎖定范圍。沒(méi)錯(cuò)芦圾，如同之前二分法的邏輯蛾派，第一個(gè)球扔在了50樓，那么他無(wú)論破碎與否个少，都幫我們排除掉了50層的問(wèn)題洪乍，這就順利的把球從100層鎖定在了50層以內(nèi)。然而球會(huì)碎的邏輯夜焦，阻礙了二分法的繼續(xù)進(jìn)行壳澳。而球會(huì)碎這個(gè)初始條件，也使我們發(fā)現(xiàn)茫经，無(wú)論何時(shí)钾埂，第一個(gè)球碎掉之后，第二個(gè)球都需要從區(qū)間的最底部開始一層一層的測(cè)試科平，直到試到上一個(gè)球碎掉所在樓層-1的樓層。
? ? 這時(shí)候問(wèn)題就開始有眉目了姜性。在1球沒(méi)碎的樓層到1球碎掉的樓層之間瞪慧，用2球一層一層的測(cè)試，直到測(cè)試出臨界樓層——這其實(shí)就是我們的最優(yōu)子結(jié)構(gòu)——在1球確定的范圍內(nèi)部念，用2球逐層檢查弃酌。所以我們可以先從最初開始算起，假設(shè)1球上來(lái)就碎掉了：
總次數(shù) = 2球測(cè)試的層數(shù) = （1球選擇的層數(shù)） - 1
而反之儡炼，如果1球第一次沒(méi)有碎掉呢妓湘？那么這個(gè)算式就變成了：
總次數(shù) =?2球測(cè)試的層數(shù) +1
2球測(cè)試的層數(shù)? = （1球選擇的第二次層數(shù)） - （1球選擇的第一次層數(shù)）
再向上同理：
總次數(shù) = （1球選擇的第n次層數(shù)） - （1球選擇的第n-1次層數(shù)）+ n-1
我們肯定是希望，每次的總次數(shù)乌询，都是相等的榜贴，這樣才能保證我們代碼的一個(gè)穩(wěn)定性。因此妹田，每向上一層唬党，我們的1球選擇的層數(shù)區(qū)間，都一定會(huì)比上一次選擇的區(qū)間少1鬼佣，以保證穩(wěn)定性驶拱。
嗯……亞克西，到這里晶衷，我們已經(jīng)找到了一個(gè)合適的思路了蓝纲。那么下面阴孟，就是看如何算出這個(gè)數(shù)來(lái)了。
假設(shè)n為第一次選擇的層數(shù)税迷，那其實(shí)就可以換算成這個(gè)樣子了：
n+(n-1)+(n-2)+…+2+1 >=100
是的永丝，連代碼都不用敲了。
n+(n-1)+(n-2)+…+2+1 >=100
1+2+…+(n-2)+(n-1)+n>=100
兩式合并
(n+1)n>=200翁狐，一元二次方程了解一下类溢？
最后結(jié)果，n最小等于14（可算得出這個(gè)數(shù)了Ｂ独痢）闯冷。
由一個(gè)完全沒(méi)有頭緒的破玩意兒，讓我們通過(guò)動(dòng)態(tài)規(guī)劃的思路懈词，最終弄成了一個(gè)一元二次方程蛇耀。
老鐵們，有沒(méi)有感受到動(dòng)態(tài)規(guī)劃的魅力所在坎弯？纺涤！
