记忆化搜索（附例题HDOJ 1501 ）
记忆化搜索又称备忘录方法，是动态规划算法的变形。
记忆化搜索编写形式就是直接递归形式，自顶向下，但是加上了标记放置重复搜索、
而动态规划是通过打表的形式，自底向上
比如过去写的一篇日志《矩阵连乘问题》http://www.cnblogs.com/liushang0419/archive/2011/04/27/2030970.html
如果用递归形式实现的话，代码如下：
但是仔细思考可以发现，直接用递归实现的话
1 int recurMatrixChain(int i,int j){
2 if(i==j)return 0;
3 int u = recurMatrixChain(i,i)+recurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];
4 s[i][j]=i;
5 for(int k=i+1;k<j;k++){
6 //直接递归的形式，自顶向下
7 int t = recurMatrixChain(i,k)+recurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];
8 if(t<u){
9 u=t;
10 s[i][j]=k;
11 }
12 }
13 return u;
14 }
有很多子问题被重复的计算，举一个例子，计算A[1 : 4]的递归树如下：
改进方法，加上备忘录，改为记忆搜索：
1 bool m[MAX][MAX];//记录是否查过,0未查，>0则查过
2 memset(m,false,sizeof(m));//最初都未查
3 int recurMatrixChain(int i,int j){
4 if(i==j)return 0;//递归边界
5 if(m[i][j])return m[i][j];//查过，直接跳出
6 int u = recurMatrixChain(i,i)+recurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];
7 s[i][j]=i;
8 for(int k=i+1;k<j;k++){
9 //直接递归的形式，自顶向下
10 int t = recurMatrixChain(i,k)+recurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];
11 if(t<u){
12 u=t;
13 s[i][j]=k;
14 }
15 }
16 m[i][j]=u;//标记此形式查过
17 }
实际应用 HDOJ 1501
http://acm.hdu.edu.cn/showproblem.php?pid=1501
题目大意，给定三个字符串，例如cat tree tcraete
问第三个是否能有第一个和第二个构成，条件，每个字符串原本的先后顺序不能变
此代码输出了正确结果，不过总是报这个错误：Output Limit Exceeded 不晓得啥意思，如果谁晓得的话，麻烦留下言，3Q
1 #include<iostream>
2 using namespace std;
3 bool dp[201][201];//记忆化搜索，存储该状态是否检索过
4 char fir[201],sec[201],thi[201];
5 int n,firLen,secLen,thiLen;
6 bool isOk;
7 void dfs(int i,int j,int k){
8 if(k==thiLen){
9 isOk=true;
10 return;
11 }
12 if(isOk)return ;//已经找到，直接跳出
13
14 if(dp[i][j])return;//该状态搜索过直接跳出
15
16 if(i<firLen&&fir[i]==thi[k])
17 dfs(i+1,j,k+1);
18 if(j<secLen&&sec[j]==thi[k])
19 dfs(i,j+1,k+1);
20
21 dp[i][j]=true;//做上标记，表明此状态扩展开的dfs都搜过了
22
23 }
24
25 int main(){
26 while(scanf("%d",&n)!=EOF){
27 for(int i=1;i<=n;i++){
28 isOk=false;
29 memset(dp,false,sizeof(dp));
30 scanf("%s%s%s",fir,sec,thi);
31
32 firLen=strlen(fir);
33 secLen=strlen(sec);
34 thiLen=strlen(thi);
35
36 dfs(0,0,0);
37 cout<<"Data set "<<i<<":";
38 cout<<(isOk?"yes":"no")<<endl;
39 }
40 }
41 return 0;
42 }
推荐.NET配套的通用数据层ORM框架：CYQ.Data 通用数据层框架
"
Anonymous[Register][218.201.115.*]2014/11/13 21:26:45#3