論記憶化搜索

什 么是記憶化搜索呢？搜索的低效在于沒有能夠很好地處理重疊子問題；動態規劃雖然比較好地處理了重疊子問題，但是在有些拓撲關系比較復雜的題目面前，又顯得 無奈。記憶化搜索正是在這樣的情況下產生的，它采用搜索的形式和動態規劃中遞推的思想將這兩種方法有機地綜合在一起，揚長避短，簡單實用，在信息學中有著 重要的作用。用一個公式簡單地說：記憶化搜索=搜索的形式+動態規劃的思想。

以 上的定義是抄的，說的非常神奇。一開始啊，我也不理解。因為我是遇到某些題然后百度到的。經過學習，我發現，所謂記憶化搜索說白了就是暴力枚舉。只不過略 微優雅一點，把算過的，有可能發生重復的部分進行記憶，不要發生重復計算即可。這就是所謂的記憶化搜索，這是我的理解。

在學習它的過程中，人們總要講到什么是動態規劃，講到普通的搜索。而在看麻省理工學院公開課：計算機科學及編程導論第13集的時候（http://v.163.com/movie/2010/6/8/1/M6TCSIN1U_M6TCT9E81.html），講的動態規劃引言就是一個默記法（記憶化搜索）。

好了說了這么多，我們看題吧：

第一題：HDU 1501(http://acm.hdu.edu.cn/showproblem.php?pid=1501)

/** 此題使用記憶化搜索* 事實證明，有的時候你覺得不可能重復的地方* 在經過大型擴展之后，會重復的非常厲害！需要自己作出判斷* 最后在說：所謂記憶化搜索，就是暴力枚舉。。。。。*/#include<stdio.h> #include<string.h>char s1[1000],s2[1000],s3[1000]; int a[201][201];//記憶化搜索，存儲該狀態是否檢索過 int len1,len2,len3;int dp(int i, int j, int k) {//printf("%d%d %d\n",i,j,k);if(a[i][j]!=-1)return a[i][j];a[i][j] = 0;if(k>=len3)return 1;elseif(i<len1&&j<len2&&s1[i]==s3[k]&&s2[j]==s3[k])return a[i][j]= dp(i+1,j,k+1)+dp(i,j+1,k+1);elseif(i<len1&&s1[i]==s3[k])return a[i][j]= dp(i+1,j,k+1);elseif(j<len2&&s2[j]==s3[k])return a[i][j]= dp(i,j+1,k+1);elsereturn a[i][j]= 0; }int main() {int n;while(scanf("%d",&n)!=EOF){int i;for(i=0;i<n;i++){memset(a,-1,sizeof(a));scanf("%s%s%s",s1,s2,s3);len1 =strlen(s1);len2 =strlen(s2);len3 =strlen(s3);if(dp(0,0,0)>0)printf("Data set %d: yes\n",i+1);elseprintf("Data set %d: no\n",i+1);}}}

第二題：UVA10003

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=944

/** 這道題用的記憶化搜索* 說白了就是暴力枚舉，然后找出最佳結果* 找的過程中注意使用默記法而已。。。。。* 這道題的原型是《最佳矩陣乘法》* 大致過程為每一步尋找一個最佳中位點，然后遞歸的找* 出來的結果是最終結果* 核心是dp函數*/ #include<stdio.h> #include<string.h> #define MAX 0x7fffffff int f[60][60],L,N,ans,c[60]; void input() {scanf("%d",&N);int t;c[0]=0;c[N+1]=L;for(inti=1;i<=N;i++){scanf("%d",&c[i]);} } int dp(int i,int j) {if(f[i][j]!=-1)return f[i][j];else if(i==j-1)returnf[i][j]=0;else {f[i][j]=MAX;int t;for(intk=i+1;k<j;k++){t=dp(i,k)+dp(k,j)+c[j]-c[i];if(f[i][j]>t)f[i][j]=t;}return f[i][j];} } void solve() {memset(f,-1,sizeof(f));ans=dp(0,N+1); } void output() {printf("Theminimum cutting is %d.\n",ans); } int main() {while(scanf("%d",&L)!=EOF && L!=0){input();solve();output();}}

其中第二題是百度的答案，我第一次碰到的記憶化搜索題。

實話說，劉汝佳的UVA題還是挺好的。

轉載于:https://www.cnblogs.com/nbalive2001/p/3204167.html

總結

以上是生活随笔為你收集整理的论记忆化搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。