什么是記憶化搜索？記憶化搜索在本質(zhì)上，還是動態(tài)規(guī)劃，只是實(shí)現(xiàn)方式采用了深度優(yōu)先搜索的形式，但是它不像深度優(yōu)先搜索那樣重復(fù)枚舉所有情況，而是把已經(jīng)計(jì)算的子問題保存下來，這樣就和動態(tài)規(guī)劃的思想不謀而合了。

本篇文章會通過最簡單的例子對記憶化搜索進(jìn)行深入講解，幫助大家學(xué)會什么是記憶化搜索。

一、記憶化搜索

記憶化搜索是一種搜索的形式，對搜索的結(jié)果用數(shù)組或其他數(shù)據(jù)結(jié)構(gòu)記錄下來。若當(dāng)前狀態(tài)搜索過了，則返回已存儲的答案。這樣，每個(gè)狀態(tài)最多計(jì)算1次。

我們以斐波那契數(shù)列為例，用遞歸實(shí)現(xiàn)的fib數(shù)組計(jì)算代碼是這樣的：

int fib(int xn){
	if(n==1||n==2){
		return 1;
	}
	return fib(n-1)+fib(n-2);
}

搜索樹是長這樣的

我們可以發(fā)現(xiàn)，為了求Fib(5)，會先求Fib(4)，然后求出Fib(3)，在求Fib(4)的時(shí)候，實(shí)際上已經(jīng)把Fib(3)求出來了，而求Fib(5)，又計(jì)算了一次，這些計(jì)算是多余的，因?yàn)椴还茉谌魏吻闆r下計(jì)算出的Fib(3)，結(jié)果都一模一樣。

所以，我們求出Fib(x)后，用一個(gè)數(shù)組F[x]來記錄這個(gè)數(shù)，如果以后需要Fib(x)的值，直接從數(shù)組中取出就可以了。

代碼如下：

#include <iostream>
using namespace std;
const int mod = 1000000009;
int f[10000];
int fib(int x) {
    if(f[x]){
        return f[x];
    }
    if (x <= 2) {
        return f[x]=1;
    }
    else {
        return f[x]=(fib(x - 1) + fib(x - 2))%mod;
    }
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

二、記憶化搜索與動態(tài)規(guī)劃

相比較于記憶化搜索，動態(tài)規(guī)劃一般要遍歷所有的狀態(tài)，神之包括一些不可行的狀態(tài)，而記憶化搜索可以進(jìn)行剪枝包括可行性剪枝、最優(yōu)性剪枝等，避免了一些多余的計(jì)算。

記憶化搜索的程序思路好想但容易寫錯(cuò)，通常代碼要短一些。

對比如下：

三、滑雪問題（記憶化搜索）

XXX喜歡滑雪，這并不奇怪， 因?yàn)榛┑拇_很刺激?？墒菫榱双@得速度，滑的區(qū)域必須向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡或者等待YYY來載你。XXX想知道載一個(gè)區(qū)域中最長的滑坡。

區(qū)域由一個(gè)二維數(shù)組給出。數(shù)組的每個(gè)數(shù)字代表點(diǎn)的高度。下面是一個(gè)例子：

XXX可以從某個(gè)點(diǎn)滑向上下左右相鄰四個(gè)點(diǎn)之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23-…-3-2-1更長。事實(shí)上，這是最長的一條。

【輸入格式】

輸入的第一行表示區(qū)域的行數(shù)R和列數(shù)C(1 <= R,C <= 500)。下面是R行，每行有C個(gè)整數(shù)，代表高度h，0<=h<=10000。

【輸出格式】

輸出最長區(qū)域的長度。

【輸入輸出樣例 1】

input

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

output

25

時(shí)間限制：2s

空間限制：128MB

題解：

本題的測試數(shù)據(jù)有著一定的誤導(dǎo)性，有些人在開始會直接出現(xiàn)兩個(gè)錯(cuò)誤思路：

（1）從單個(gè)或多個(gè)最高點(diǎn)開始的路徑一定最長

（2）每次選擇與當(dāng)前點(diǎn)落差最小的點(diǎn)作為下一個(gè)點(diǎn)的路徑一定最長

（3）前兩種思路全部出現(xiàn)

這三種情況實(shí)際上只要稍稍想一想就能發(fā)現(xiàn)反例，就看你能否仔細(xì)思考反問了

正解：記憶化搜索

爆搜思路：將每個(gè)點(diǎn)作為起始點(diǎn)，向四個(gè)方向中合法的點(diǎn)試最長路徑，這樣有多層嵌套循環(huán)的題目，單純的爆搜基本上都會爆時(shí)間 有空可以算一下，所以需要在DFS時(shí)帶上記憶化，用全局?jǐn)?shù)組記錄每個(gè)點(diǎn)自身為起始點(diǎn)時(shí)的最長路徑，需要時(shí)直接取用，更詳細(xì)請看下面代碼與注釋

#include<bits/stdc++.h>
using namespace std;
typedef struct node
{
	int h,path;//h：此點(diǎn)的高度，path：以該點(diǎn)為起始點(diǎn)時(shí)的最長路徑
}NODE,*PNODE;
NODE a[501][501];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0},n,m;
int calc(int x,int y)
{
	if(a[x][y].path)
		return a[x][y].path;//如果已經(jīng)有了路徑，直接返回即可，非常省時(shí)
	int i,x1,y1,maxx=0,t;
	for(i=0;i<4;i++)
	{
		x1=x+dx[i];
		y1=y+dy[i];//下一個(gè)點(diǎn)
		if(x1>0&&x1<=n&&y1>0&&y1<=m&&a[x1][y1].h<a[x][y].h)//判斷下一個(gè)點(diǎn)是否合法，注意：只要是比當(dāng)前點(diǎn)低的點(diǎn)都要進(jìn)
		{
			t=calc(x1,y1);//繼續(xù)遞歸計(jì)算
			maxx=max(maxx,t);//更新最大路徑
		}
	}
	return a[x][y].path=maxx+1;//這里處理的稍微簡潔了一點(diǎn)
}
int main()
{
	int i,j,t,ans=0;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j].h);//接收數(shù)據(jù)
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			t=calc(i,j);
			ans=max(ans,t);
		}
	printf("%d",ans);
	return 0;
}