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

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

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

intfind(inti,intj){ //向4個方向嘗試 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 問題上面的做法可以得到最優(yōu)解，但有一個問題。如下例，以15為起點的時候，會嘗試把6->5->4->3->2->1走一遍。但以16為起點的時候，還會嘗試把這條路線走一遍，這就會導(dǎo)致大量的重復(fù)計算。 ?那能不能優(yōu)化呢？ 之所以重復(fù)計算，是因為每一次嘗試都是重新的開始，它并不知道這條路已經(jīng)走過了，也就是沒有記憶，所以我們引入一種優(yōu)化的方法，就是記憶化搜索。 04 記憶化搜索可以引入一個f[i][j]數(shù)組，記錄以(i,j)為起點所能找到的最長路線的長度，初始賦值為-1，表示還沒有走過。 ?當(dāng)走過一點，就將對應(yīng)的f[i][j]更新為以(i,j)為起點的最大長度。 再回到上面的問題，因為之前肯定走過了(2,3)，對應(yīng)的f[2][3]為6，當(dāng)嘗試從(2,4)出發(fā)時，會發(fā)現(xiàn)周圍已經(jīng)走過了，只需要更新當(dāng)前的值+1即可，就避免了重復(fù)計算。 ? ?05 代碼實現(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é)記憶化搜索是一種非常實用的算法，因為深搜用遞歸很容易實現(xiàn)，記憶化又避免了重復(fù)子問題的計算，提高了運行效率。 這其實就是動態(tài)規(guī)劃的思想，常見的動態(tài)規(guī)劃用遞推實現(xiàn)，相比記憶化搜索實現(xiàn)上會更難一點，而記憶化搜索就沒有這個問題。 算法的適用場景也需要根據(jù)具體的問題來分析，一般常用在地圖或者樹型結(jié)構(gòu)中。 審核編輯 ：李倩