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

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

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

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 問題上面的做法可以得到最優解，但有一個問題。如下例，以15為起點的時候，會嘗試把6->5->4->3->2->1走一遍。但以16為起點的時候，還會嘗試把這條路線走一遍，這就會導致大量的重復計算。 ?那能不能優化呢？ 之所以重復計算，是因為每一次嘗試都是重新的開始，它并不知道這條路已經走過了，也就是沒有記憶，所以我們引入一種優化的方法，就是記憶化搜索。 04 記憶化搜索可以引入一個f[i][j]數組，記錄以(i,j)為起點所能找到的最長路線的長度，初始賦值為-1，表示還沒有走過。 ?當走過一點，就將對應的f[i][j]更新為以(i,j)為起點的最大長度。 再回到上面的問題，因為之前肯定走過了(2,3)，對應的f[2][3]為6，當嘗試從(2,4)出發時，會發現周圍已經走過了，只需要更新當前的值+1即可，就避免了重復計算。 ? ?05 代碼實現路線搜索

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函數

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 總結記憶化搜索是一種非常實用的算法，因為深搜用遞歸很容易實現，記憶化又避免了重復子問題的計算，提高了運行效率。 這其實就是動態規劃的思想，常見的動態規劃用遞推實現，相比記憶化搜索實現上會更難一點，而記憶化搜索就沒有這個問題。 算法的適用場景也需要根據具體的問題來分析，一般常用在地圖或者樹型結構中。 審核編輯 ：李倩