01 故事起源有一天小K去滑雪，雪山高低不平，當(dāng)然小K只能從高的地方向低的地方滑，那如何選擇路線才能滑的最遠(yuǎn)呢？ 把這個(gè)問(wèn)題抽象描述如下：

在一個(gè)二維地圖中，數(shù)值代表此處山的高度，在某個(gè)點(diǎn)只能滑向上下左右4個(gè)相鄰的點(diǎn)，最遠(yuǎn)的滑行路線，也就等價(jià)于找出一條最長(zhǎng)的數(shù)值下降路線。

比如下圖中的紅色路線就是此時(shí)最長(zhǎng)的一條路線，長(zhǎng)度為10。那要如何找出這樣的一條路線呢？ ? ?02 分析在每個(gè)點(diǎn)上，只能向周圍4個(gè)方向滑行，當(dāng)然前提是此處的高度必須比周圍高。 ?我們當(dāng)然可以選擇盡可能高的位置出發(fā)，比如圖中17比15要高。 ?但這種有可能會(huì)陷入局部最優(yōu)解，比如從下圖中的15開(kāi)始，最大長(zhǎng)度為2。而從13開(kāi)始會(huì)更優(yōu)，長(zhǎng)度為5。 ?所以啟示我們，不能簡(jiǎn)單的貪心，而是要考慮全局最優(yōu)，因?yàn)槊恳粋€(gè)起點(diǎn)都有可能是最優(yōu)的起點(diǎn)。
那就有了初步的框架了，從每一個(gè)起點(diǎn)出發(fā)，把可行的路線都找出來(lái)，也就是能走的路線都走一遍，再比較全局最優(yōu)的就行了，而且這也正好符合深搜的算法框架。偽代碼

intfind(inti,intj){ //向4個(gè)方向嘗試 for(i=0->3){ if(ok){ returnfind(next)+1 } } } intmain(){ for(i=0->n){ for(j=0->m) { t=find(i,j) ans=max(ans,t) } } } 03 問(wèn)題上面的做法可以得到最優(yōu)解，但有一個(gè)問(wèn)題。如下例，以15為起點(diǎn)的時(shí)候，會(huì)嘗試把6->5->4->3->2->1走一遍。但以16為起點(diǎn)的時(shí)候，還會(huì)嘗試把這條路線走一遍，這就會(huì)導(dǎo)致大量的重復(fù)計(jì)算。 ?那能不能優(yōu)化呢？ 之所以重復(fù)計(jì)算，是因?yàn)槊恳淮螄L試都是重新的開(kāi)始，它并不知道這條路已經(jīng)走過(guò)了，也就是沒(méi)有記憶，所以我們引入一種優(yōu)化的方法，就是記憶化搜索。 04 記憶化搜索可以引入一個(gè)f[i][j]數(shù)組，記錄以(i,j)為起點(diǎn)所能找到的最長(zhǎng)路線的長(zhǎng)度，初始賦值為-1，表示還沒(méi)有走過(guò)。 ?當(dāng)走過(guò)一點(diǎn)，就將對(duì)應(yīng)的f[i][j]更新為以(i,j)為起點(diǎn)的最大長(zhǎng)度。 再回到上面的問(wèn)題，因?yàn)橹翱隙ㄗ哌^(guò)了(2,3)，對(duì)應(yīng)的f[2][3]為6，當(dāng)嘗試從(2,4)出發(fā)時(shí)，會(huì)發(fā)現(xiàn)周圍已經(jīng)走過(guò)了，只需要更新當(dāng)前的值+1即可，就避免了重復(fù)計(jì)算。 ? ?05 代碼實(shí)現(xiàn)路線搜索

intfind(vector<vector<int>>&snowMountain,vector<vector<int>>&f,inti,intj,intr,intc){ intx,y; if(f[i][j]!=-1) returnf[i][j]; f[i][j]=1; for(intk=0;k4;k++){ x=i+direction[k][0]; y=j+direction[k][1]; //validdirection if(x>=0&&x=0&&ysnowMountain[x][y]){ f[i][j]=maxOfTwo(f[i][j],find(snowMountain,f,x,y,r,c)+1); } } returnf[i][j]; }main函數(shù)

intmain(){ ifstreamfin("a.in"); ofstreamfout("a.out"); inti,j,r,c,maxHeight=0; fin>>r>>c; vector<vector<int>>snowMountain(r,vector<int>(c,0)); vector<vector<int>>f(r,vector<int>(c,-1)); for(i=0;ifor(j=0;j>snowMountain[i][j]; for(i=0;ifor(j=0;jendl; fin.close(); fout.close(); return0; } 06 總結(jié)記憶化搜索是一種非常實(shí)用的算法，因?yàn)樯钏延眠f歸很容易實(shí)現(xiàn)，記憶化又避免了重復(fù)子問(wèn)題的計(jì)算，提高了運(yùn)行效率。 這其實(shí)就是動(dòng)態(tài)規(guī)劃的思想，常見(jiàn)的動(dòng)態(tài)規(guī)劃用遞推實(shí)現(xiàn)，相比記憶化搜索實(shí)現(xiàn)上會(huì)更難一點(diǎn)，而記憶化搜索就沒(méi)有這個(gè)問(wèn)題。 算法的適用場(chǎng)景也需要根據(jù)具體的問(wèn)題來(lái)分析，一般常用在地圖或者樹(shù)型結(jié)構(gòu)中。 審核編輯 ：李倩