六月中旬了，马上就要期末考试了，期末考试结束以后就要迎来紧张刺激的留校集训，到那时博客会更新的比较频繁，而现在在准备期末考试，所以可能更新的博客稍微少一些。
话不多说，今天来更一篇刚刚吃饭的时候关于记忆化搜索和动态规划的一些区别的思考。
记忆化搜索（Memory Search），其实还是用递归函数实现的，通常函数名依然叫做dfs（ ￣□￣｜｜）。核心语句就是那两部分关键的语句块啦。
1.函数一开始的判断出口：if(搜索过) return 数组中的值。因为这里涉及到是否搜索过，所以一般将数组初始化为-1，详情见那道经典的滑雪题目：链接稍后送上。那道滑雪题，也可以用dp解，他俩的区别和解题的不同一会博客中也会有提到。
2.函数的递归前进语句：return fib[i]=fib[i-1]+fib[i-2];（没有具体的例子实在不好说了，所以这里用fib数列来做演示）。
这样就做到了数组的每个值只计算了一次，不会有多余的时间消耗。
还有一点！记住ms型dfs就必须是int型的了！！ 不要在用bool或者void了！
下面送上记忆化搜索的fib求解的部分代码：
#include<iostream>
using namespace std;
const int MAX = 10000+5;
int fib[MAX];
int dfs(int n) {//
if(fib[n]!=-1) return fib[n];
return fib[n]=dfs(n-1)+dfs(n-2);
}
int main()
{
fib[1]=fib[2]=1;
for(int i = 2; i<MAX; i++) {
fib[i]=-1;
}
dfs(MAX-1);//别写成了MAX，那样输出的全是-1
for(int i = 1; i<=50; i++) {
printf("%d ",fib[i]);
if(i%5==0) {
printf("\n");
}
}
return 0 ;
} 输出结果：
1 1 2 3 5
8 13 21 34 55
89 144 233 377 610
987 1597 2584 4181 6765
10946 17711 28657 46368 75025
121393 196418 317811 514229 832040
1346269 2178309 3524578 5702887 9227465
14930352 24157817 39088169 63245986 102334155
165580141 267914296 433494437 701408733 1134903170
1836311903 -1323752223 512559680 -811192543 -298632863下面是一个很值特研究的问题：
为什么说能用dp的都能用ms，但是反之不立。（至少我是这么认为的）
在fib中，你会发现写记忆化搜索像个傻子一样自取麻烦，直接dp递推多简单，多此一举。但之所以在fib中ms和dp如此相似是因为fib的顺序是固定的！有规律的！所以体现不出ms的用处来！
再看一道题比如滑雪，你如果用dp，必须要排序！然后按照排序的顺序（那道题是按照高度排序的）从小到大递推！原因也很简单，因为dp[i][j]可能需要用到四周的值！且dp有个特点，我既然要用你，那么你的值，比如要是已经确定的值（就是不会再更新这个值了），我给他取个名叫完成值，并给他一个特点，那就是，你如果是完成值，那么你将不会再被更新了，也就是，对这个数据，只有读的功能，没有写的功能。也就是说，比如if(i,j右边那个点的高度（即i,j+1）<当前i,j坐标的高度)，那么更新dp[i][j]，并且dp[i][j]也是完成值了！（通过判断是不是-1来确定是否是完成值，因为最开始初始化成-1），而如果i,j右边那个点的高度（即i,j+1）<当前i,j坐标的高度，那就无所谓i,j+1是不是完成值了，，，反正你也不去读这个数据（刚刚说过了对完成值只能读不能写！）所以你需要用到的值，都是高度比你小的值，这也是为什么需要进行按照高度从小到大进行排序，并且递推的时候，只能按照这个顺序进行递推！
上面一段是你如果用dp的情况，而如果你用的是ms，情况将没这么复杂，不需要排序！不需要按照一定顺序递推！而只需要上面提到的两条关键的语句块，就解决的所有事情！具体还是需要自己体会的。、。。
下面贴上滑雪的ms代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int r,c;
int maze[105][105];
int dp[105][105];
void init () {
for(int i = 1; i<=104 ; i++) {
for(int j = 1 ; j<=104 ; j++) {
dp[i][j]=-1;
}
}
}
bool ok(int x,int y){
if(x<=r&&x>0&&y<=c&&y>0) return true;
else return false;
}
int dfs(int x,int y) {
if(dp[x][y]!=-1) {
return dp[x][y];
}
// if(x==0||y==0) return 0 ;
int flag=0;
int next[4]={0,0,0,0};
if(maze[x+1][y]<maze[x][y]&&ok(x+1,y)) {
next[0]=dfs(x+1,y);
flag=1;
}
if(maze[x][y+1]<maze[x][y]&&ok(x,y+1)) {
next[1]=dfs(x,y+1);
flag=1;
}
if(maze[x-1][y]<maze[x][y]&&ok(x-1,y)) {
next[2]=dfs(x-1,y);
flag=1;
}
if(maze[x][y-1]<maze[x][y]&&ok(x,y-1)) {
next[3]=dfs(x,y-1);
flag=1;
}
if(flag==0) return dp[x][y]=0;
return dp[x][y]=1+*max_element(next,next+4);
}
int main()
{
cin >> r>>c;
int maxx=0;
init();
for(int i=1; i<=r; i++) {
for(int j = 1 ; j<=c ; j++) {
scanf("%d",&maze[i][j]);
}
}
for(int i=1; i <= r ; i++) {
for(int j = 1 ; j <= c ; j++) {
maxx=max(maxx,dfs(i,j));
}
}
cout << maxx+1<<endl;
return 0 ;
} 
京公网安备 11010502036488号