記憶化搜索的應用
一般來說，動態規劃總要遍歷所有的狀態，而搜索可以排除一些無效狀態。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。
如何協調好動態規劃的高效率與高消費之間的矛盾呢？有一種折中的辦法就是記憶化算法。記憶化算法在求解的時候還是按著自頂向下的順序，每求解一個狀態，就將它的解保存下來，以后再次遇到這個狀態的時候，就不必重新求解了。這種方法綜合了搜索和動態規劃兩方面的優點，因而還是很有使用價值的。
舉一個例子：如右圖所示是一個有向無環圖，求從頂點1到頂點6的最長路徑。（規定邊的方向從左到右）
我們將從起點（頂點1）開始到某個頂點的最長路徑作為狀態，用一維數組opt記錄。Opt[j]表示由起點到頂點j時的最長路徑。顯然，opt[1]=0，這是初始狀態，即動態規劃的邊界條件。于是，我們很容易地寫出狀態轉移方程式：opt[j]=max{opt[k]+a[k,j]}（k到j有一條長度為a[k,j]的邊）。雖然有了完整的狀態轉移方程式，但是還是不知道動態規劃的順序。所以，還需要先進行一下拓撲排序，按照排序的順序推下去，opt[6]就是問題的解。
可以看出，動態規劃相比搜索之所以高效，是因為它將所有的狀態都保存了下來。當遇到重復子問題時，它不像搜索那樣把這個狀態的最優值再計算一遍，只要把那個狀態的最優值調出來就可以了。例如，當計算opt[4]和opt[5]時，都用到了opt[3]的值。因為已經將它保存下來了，所以就沒有必要再去搜索了。
但是動態規劃仍然是有缺點的。一個很突出的缺點就是要進行拓撲排序。這道題的拓撲關系是很簡單的，但有些題的拓撲關系是很復雜的。對于這些題目，如果也進行拓撲排序，工作量非常大。遇到這種情況，我們可以用記憶化搜索的方法，避免拓撲排序。
【例】滑雪
【問題描述】
小明喜歡滑雪，因為滑雪的確很刺激，可是為了獲得速度，滑的區域必須向下傾斜，當小明滑到坡底，不得不再次走上坡或等著直升機來載他，小明想知道在一個區域中最長的滑坡。滑坡的長度由滑過點的個數來計算，區域由一個二維數組給出，數組的每個數字代表點的高度。下面是一個例子：
1???? 2???? 3???? 4???? 5
16??? 17??? 18??? 19??? 6
15??? 24??? 25??? 20??? 7
14??? 23??? 22??? 21??? 8
13??? 12??? 11??? 10??? 9
一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小，在上面的例子中，一條可行的滑坡為25-24-17-16-1（從25開始到1結束），當然25-24……2…1更長，事實上這是最長的一條。
【輸入格式】
輸入的第一行為表示區域的二維數組的行數R和列數C（1≤R、C≤100），下面是R行，每行有C個數代表高度。
【輸出格式】
輸出區域中最長的滑坡長度。
【輸入樣例】ski.in
5????? 5
1????? 2???? 3???? 4???? 5
16??? 17? ??18??? 19??? 6
15??? 24??? 25??? 20??? 7
14??? 23??? 22??? 21??? 8
13??? 12??? 11??? 10??? 9
【輸出樣例】ski.out
25
【算法分析】
由于一個人可以從某個點滑向上下左右相鄰四個點之一，如上圖所示。當且僅當高度減小，對于任意一個點[i,j]，當它的高度小于與之相鄰的四個點（[i-1,j], [i,j+1], [i+1,j], [i,j-1]）的高度時，這四個點可以滑向[i,j]，用f[i,j]表示到[i,j]為止的最大長度，則f[i,j]=max{f（i+a,j+b）}+1，其中坐標增量{(a,b)=[(1,0),(-1,0),(0,1),(0,-1)],0<i+a<=r，0<j+b<=c，High[i,j]<High[i+a,j+b]}。為了保證滿足條件的f[i+a,j+b]在f[i,j]前算出，需要對高度排一次序，然后從大到小規劃（高度）。最后再比較一下所有f(i,j){0<i≤r,0<j≤c}，找出其中最長的一條路線。我們還可以用記憶化搜索的方法，它的優點是不需進行排序，按照行的順序，利用遞歸逐點求出區域中到達此點的最長路徑，每個點的最長路徑只求一次。
1 const
2 dx:array[1..4] of shortint=(0,-1,0,1); {x的坐標增量}
3 dy:array[1..4] of shortint=(-1,0,1,0); {y的坐標增量}
4 var
5 r,c,ans,anss:longint;
6 map,f:array[1..100,1..100] of longint;
7 procedure init;
8 var i,j:longint;
9 begin
10 readln(r,c);
11 for i:=1 to r do
12 for j:=1 to c do
13 read(map[i,j]); {讀入每個點的高度}
14 ans:=0; anss:=0;
15 fillchar(f,sizeof(f),0);
16 end;
17 function search(x,y:longint):longint; {函數的作用是求到[x,y]點的最長路徑}
18 var i,j,nx,ny,tmp,t:longint;
19 begin
20 if f[x,y]>0 then {此點長度已經求出，不必進行進一步遞歸，保證每一個點的最大長度只求一次，這是記憶化搜索的特點}
21 begin
22 search:=f[x,y]; exit;
23 end;
24 t:=1;
25 for i:=1 to 4 do {從四個方向上搜索能達到[x,y]的點}
26 begin
27 nx:=x+dx[i]; ny:=y+dy[i]; {新坐標}
28 if (1<=nx)and(nx<=r) and (1<=ny)and(ny<=c) {邊界限制}
29 and (map[nx,ny]>map[x,y]) {高度比較}
30 then
31 begin
32 tmp:=search(nx,ny)+1; {遞歸進行記憶化搜索}
33 if tmp>t then t:=tmp;
34 end;
35 end;
36 f[x,y]:=t;
37 search:=t;
38 end;
39 procedure doit;
40 var i,j:longint;
41 begin
42 for i:=1 to r do {按照行的順序，利用遞歸逐點求出區域中到達此點的最長路徑}
43 for j:=1 to c do
44 begin
45 anss:=search(i,j);
46 //f[i,j]:=anss;
47 if anss>ans then ans:=anss; {尋找最大長度值}
48 end;
49 end;
50 procedure outit;
51 var i,j:longint;
52 begin
53 {for i:=1 to r do begin
54 for j:=1 to c do
55 write(f[i,j],' '); writeln; end;}
56 writeln(ans);
57 end;
58 begin
59 init;
60 doit;
61 outit;
62 end. ?
