琪琪先锋 torrent magnet,中文字幕人妻丰满熟妇,美女扒开粉嫩尿囗桶爽免费网站,成人性爱免费视频,日韩午夜,欧美爱爱视频,精品三级在线观看,久久天堂网

青蛙的故事

青蛙公主是遠(yuǎn)近聞名的大美蛙??，她一心想找一個(gè)聰明的老公，于是設(shè)下擂臺(tái)，比武招親：有連續(xù)的木板，因?yàn)椴馁|(zhì)不同，每個(gè)木板能跳的最大距離有限，來(lái)應(yīng)招的青年才俊，需要判斷，是否能跳到最后一塊板子。

讓我們來(lái)看看輸入參數(shù)：一個(gè)非負(fù)整數(shù)數(shù)組，青蛙位于數(shù)組的第一個(gè)位置，數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。輸出就更簡(jiǎn)單：能否跳到。

解題思路

按照一般的解題思維，DFS肯定可以做，但效率應(yīng)該不是最高。遞推的話(huà)，動(dòng)態(tài)規(guī)劃可以考慮，同時(shí)看看有沒(méi)有使用貪心算法的可能性，如果能貪心，那可能就是最簡(jiǎn)路徑。

很幸運(yùn)，這道題無(wú)論是DFS，還是動(dòng)態(tài)規(guī)劃，亦或是貪心算法都可以做，我比較喜歡這類(lèi)題，從不同思路，開(kāi)展不同做法，互相比較，歸納復(fù)盤(pán)，容易得到提高。話(huà)不多說(shuō)，我們來(lái)逐個(gè)看看。

花式吊打

DFS深度優(yōu)先算法

最直接的解法，就是基于每種可能，即每塊板子可能的跳躍距離，進(jìn)行DFS遞歸搜索。這種算法思路比較無(wú)腦，缺點(diǎn)顯而易見(jiàn)：時(shí)間復(fù)雜度很高，大概率會(huì)超時(shí)。

換個(gè)角度：目標(biāo)是最后一個(gè)木板。那么往前找到所有能跳到目標(biāo)的木板，然后以這些木板為目標(biāo)，遞歸查找下去。這種算法速率也一般，算是優(yōu)化版的DFS。

果不其然，運(yùn)行超時(shí)，蛙蛙流淚。

動(dòng)態(tài)規(guī)劃

我們定義一個(gè)數(shù)組dp，dp[i]表示當(dāng)前可以覆蓋的最大范圍。當(dāng)前位置能否可達(dá)很簡(jiǎn)單，判斷dp[i-1]是否小于i，如果小于就不可達(dá)。如果可達(dá)，更新dp[i] = Max(dp[i-1], i+nums[i])。

由上圖執(zhí)行結(jié)果可以看到，按照動(dòng)態(tài)規(guī)劃執(zhí)行的數(shù)據(jù)，相比DFS是飛躍，耗時(shí)減少2/3，內(nèi)存消耗減少100%以上，時(shí)間復(fù)雜度應(yīng)該已經(jīng)是最優(yōu)，后面就看空間上是否可以?xún)?yōu)化。

貪心算法

貪心算法，顧名思義，就是足夠貪心。如果當(dāng)前木板能跳到的距離比當(dāng)前能達(dá)的距離更遠(yuǎn)，就跳到當(dāng)前木板，否則就先停留在當(dāng)前木板。按照這樣的規(guī)則，一直跳到最后一塊板，其間永遠(yuǎn)站在能跳的最遠(yuǎn)的木板。如果中間有位置不可達(dá)了，那就是跳不到，因?yàn)樵谪澬牡幕A(chǔ)上，當(dāng)前點(diǎn)已經(jīng)是覆蓋范圍最大的了，如果這樣都跳不到，其他方式也不行的。

我們能看到這樣寫(xiě)代碼，簡(jiǎn)潔優(yōu)雅，耗時(shí)滿(mǎn)足預(yù)期，寫(xiě)完給自己點(diǎn)個(gè)贊??，青蛙王子也得感謝我！

但是仔細(xì)想想，上面的代碼其實(shí)可以更簡(jiǎn)潔明了。因?yàn)樵诒绢}中跳點(diǎn)不是必要項(xiàng)，換句話(huà)說(shuō)，我們可以從關(guān)注跳點(diǎn)，變成關(guān)注距離。優(yōu)化后的代碼如下，是不是更加清晰？

把簡(jiǎn)單的事情做復(fù)雜不算什么。把復(fù)雜的事情越做越簡(jiǎn)單，才是能力提升的關(guān)鍵！

逆推法

實(shí)不相瞞，這題做到這里，還做出感覺(jué)了。我就想，還有沒(méi)有其他解決方法？

換個(gè)角度思考一下，之前大多為正向推導(dǎo)，但是DFS是逆向行走，說(shuō)明逆推是可行的，只是我們嫌棄DFS效率太低。

對(duì)于一個(gè)目標(biāo)位置，我們往前找能跳到該位置的最近的木板，將這個(gè)木板作為我們新的目標(biāo)。這樣持續(xù)倒推，如果最終推導(dǎo)到了第一塊木板，也就是我們的起點(diǎn)，那么就證明可以從起點(diǎn)跳到終點(diǎn)。

注意，我們來(lái)仔細(xì)思考下這種方式和DFS的不同，DFS是基于當(dāng)前位置，從后往前遞歸所有能跳到當(dāng)前木板的情況，會(huì)走完多條分支路徑；而這種逆推方式，只會(huì)隨遇而安地往前挪挪，是O(n)的復(fù)雜度。

蛙蛙復(fù)盤(pán)

橫看成嶺側(cè)成峰，條條大路通羅馬，一個(gè)簡(jiǎn)單的跳板運(yùn)動(dòng)，居然有這么多思維方式。把一件事情做到極致，我們也一定會(huì)收獲多多。做算法題，不僅要嘗試beats 100%，更進(jìn)一步的追求是將各種方式都做透徹，每種方式可能有自己的優(yōu)缺點(diǎn)，很可能加一個(gè)限制條件，當(dāng)前最優(yōu)解就成死路了。

當(dāng)然，最重要的是，這樣的做題習(xí)慣訓(xùn)練了我們不同思維方式。無(wú)論是在學(xué)習(xí)還是工作中，一個(gè)問(wèn)題，你能給出好幾種解決方案，還不能成為這條街上最靚的仔？