解決動(dòng)態(tài)規(guī)劃的基本步驟寿羞，分別是：設(shè)置狀態(tài)、枚舉子問(wèn)題矫废，更新答案盏缤。
其實(shí)，這每一步都不是那么好做到的蓖扑，需要有足夠的經(jīng)驗(yàn)和相關(guān)數(shù)學(xué)知識(shí)來(lái)得出并化簡(jiǎn)動(dòng)態(tài)轉(zhuǎn)移方程唉铜，這對(duì)入門選手是很不友好的。
今天律杠，我來(lái)介紹一種秒解DP的方法潭流，適合入門選手快速熟悉動(dòng)態(tài)規(guī)劃問(wèn)題，并逐步積累經(jīng)驗(yàn)柜去。
他就是——
搜索灰嫉！
搜索！
搜索嗓奢！
你可能會(huì)好奇：動(dòng)態(tài)規(guī)劃思想不就是要解決搜索算法時(shí)間復(fù)雜度過(guò)高的問(wèn)題嗎熬甫？這里怎么反而用搜索來(lái)解決動(dòng)態(tài)規(guī)劃問(wèn)題了呢？
當(dāng)然蔓罚，這里的搜索并不是普通的搜索，而是記憶化搜索瞻颂。
我們還是用01背包問(wèn)題為例子豺谈，來(lái)講解一下記憶化搜索的原理和實(shí)現(xiàn)方法。
搜索程序顯然是很容易就能寫出來(lái)的贡这，核心代碼如下：
這段代碼中茬末，step表示當(dāng)前處理到那個(gè)物品，v表示背包已用的容量盖矫，sum表示當(dāng)前背包內(nèi)物品總共的價(jià)值丽惭。搜索過(guò)程分當(dāng)前物品選或不選進(jìn)行遞歸。
這代代碼的時(shí)間復(fù)雜度是O(2^N)辈双，顯然很難接受责掏。
這時(shí)候，我們可以換一個(gè)搜索思路湃望，把尾遞歸換成首遞歸换衬。
參考一下代碼：
這段代碼也是很好理解的痰驱，step表示當(dāng)前處理的物品，v表示當(dāng)前背包剩下的容量瞳浦。
但是担映，這么修改后時(shí)間復(fù)雜度也是O(2^N)的，并沒(méi)有優(yōu)化叫潦，怎么辦呢蝇完？
我們觀察代碼，發(fā)現(xiàn)每層循環(huán)的自變量是step和v矗蕊，因變量是返回值tmp短蜕。很顯然，一旦step和v確定了拔妥，返回值tmp也就確定了忿危。
這么說(shuō)來(lái)，我們是不是開一個(gè)二維數(shù)組把tmp的值存下來(lái)没龙，就只需要計(jì)算一次就好了铺厨，省事。
核心代碼如下：
注意硬纤，f數(shù)組的初值為-1解滓。
那么，這么處理后筝家，代碼的時(shí)間復(fù)雜度還是O(2^N)嗎洼裤？
我們發(fā)現(xiàn)，如果f[step][v]不是-1（也就是已經(jīng)得出了應(yīng)該的返回值是）溪王，就會(huì)直接返回腮鞍，不會(huì)再繼續(xù)遞歸。那么莹菱，最壞情況下就是把f數(shù)組的每個(gè)值都算出來(lái)罷了移国。時(shí)間復(fù)雜度為O(NV)，和用for循環(huán)實(shí)現(xiàn)的時(shí)間復(fù)雜度是一樣的道伟，但由于搜索需要遞歸壓棧迹缀，可能常數(shù)會(huì)大一點(diǎn)。
記憶化搜索解決動(dòng)態(tài)規(guī)劃問(wèn)題是很容易理解的蜜徽。我們只需要按照寫搜索的方法先寫一個(gè)程序祝懂，然后找到自變量（其實(shí)就是遞歸參數(shù)）和因變量（每一層遞歸的返回值），就能快速實(shí)現(xiàn)記憶化搜索的程序拘鞋。
【信息學(xué)競(jìng)賽從入門到巔峰】砚蓬，一個(gè)專注于分享OI/ACM常用算法及知識(shí)的公眾號(hào)。
