聊聊动态规划与记忆化搜索

· · 算法·理论

聊聊动态规划与记忆化搜索

by \color{Gray}{InterestingLSY} (菜到发灰) ，在此一并感谢 \color{purple}{ComeIntoPower}dalao的指点qwq

想体验把暴搜改改就是正解的快感吗? 想体验状压dp看似状态多到爆炸实际一跑却嗷嗷快(实际有效的状态数很少)的荣耀吗? 记忆化搜索,符合您的需求!只要998,记忆化搜索带回家!记忆化搜索,记忆化搜索,再说一遍,记忆化搜索!

先点个赞吧(逃

由于我讲的比较磨叽,兜售目录一份,dalao们可以选择自己喜欢的部分看

目录：

1. 记忆化搜索是啥（引入

好，就以 这道题 为例，我不会动态规划，只会搜索，我就会直接写一个粗暴的 DFS :

注: 为了方便食用, 本文中所有代码省略头文件

int n,t;
int tcost[103],mget[103];
int ans = 0;
void dfs( int pos , int tleft , int tans ){
    if( tleft < 0 ) return;
    if( pos == n+1 ){
        ans = max(ans,tans);
        return;
    }
    dfs(pos+1,tleft,tans);
    dfs(pos+1,tleft-tcost[pos],tans+mget[pos]);
}
int main(){
    cin >> t >> n;
    for(int i = 1;i <= n;i++)
        cin >> tcost[i] >> mget[i];
    dfs(1,t,0);
    cout << ans << endl;
    return 0;
}

这就是个十分智障的大暴搜是吧......

emmmmmm....... \color{Red}{30} 分

然后我心血来潮, 想不借助任何 "外部变量"(就是 dfs 函数外且 值随 dfs 运行而改变的变量 ), 比如 ans

把 ans 删了之后就有一个问题: 我们拿什么来记录答案?

答案很简单:

返回值!

此时 dfs(pos,tleft) 返回在时间 tleft 内采集 后 pos 个草药, 能获得的最大收益

不理解就看看代码吧:

int n,time;
int tcost[103],mget[103];
int dfs(int pos,int tleft){
    if(pos == n+1)
        return 0;
    int dfs1,dfs2 = -INF;
    dfs1 = dfs(pos+1,tleft);
    if( tleft >= tcost[pos] )
        dfs2 = dfs(pos+1,tleft-tcost[pos]) + mget[pos];
    return max(dfs1,dfs2);
}
int main(){
    cin >> time >> n;
    for(int i = 1;i <= n;i++)
        cin >> tcost[i] >> mget[i];
    cout << dfs(1,time) << endl;
    return 0;
}

emmmmmm....... 还是 \color{Red}{30} 分

但这个时候, 我们的程序已经不依赖任何外部变量了.

然后我非常无聊, 将所有 dfs 的返回值都记录下来, 竟然发现......

震惊, 对于相同的 pos 和 tleft,dfs 的返回值总是相同的!

想一想也不奇怪, 因为我们的 dfs 没有依赖任何外部变量.

旁白: 像 tcost[103],mget[103] 这种东西不算是外部变量, 因为她们在 dfs 过程中不变.

然后?

开个数组 mem , 记录下来每个 dfs(pos,tleft) 的返回值. 刚开始把 mem 中每个值都设成 -1 (代表没访问过). 每次刚刚进入一个 dfs 前(我们的 dfs 是递归调用的嘛), 都检测 mem[pos][tleft] 是否为 -1 , 如果是就正常执行并把答案记录到 mem 中, 否则?

直接返回 mem 中的值!

int n,t;
int tcost[103],mget[103];
int mem[103][1003];
int dfs(int pos,int tleft){
    if( mem[pos][tleft] != -1 ) return mem[pos][tleft];
    if(pos == n+1)
        return mem[pos][tleft] = 0;
    int dfs1,dfs2 = -INF;
    dfs1 = dfs(pos+1,tleft);
    if( tleft >= tcost[pos] )
        dfs2 = dfs(pos+1,tleft-tcost[pos]) + mget[pos];
    return mem[pos][tleft] = max(dfs1,dfs2);
}
int main(){
    memset(mem,-1,sizeof(mem));
    cin >> t >> n;
    for(int i = 1;i <= n;i++)
        cin >> tcost[i] >> mget[i];
    cout << dfs(1,t) << endl;
    return 0;
}

此时 mem 的意义与 dfs 相同:

在时间 tleft 内采集 后 pos 个草药, 能获得的最大收益

这能 ac?

能. 这就是 "采药" 那题的 AC 代码

好我们 yy 出了记忆化搜索

总结一下记忆化搜索是啥:

2. 记忆化搜索与动态规划的关系:（分析

基本是朋 (ji) 友关系

有人会问: 记忆化搜索难道不是搜索?

一定程度上来说，她是搜索.但个人认为她更像dp

其实说白了，记忆化搜索就是dp

不信你看mem 的意义:

在时间 tleft 内采集 后 pos 个草药, 能获得的最大收益

这不就是dp的状态?

由上面的代码中可以看出:

dfs(pos,left) = max(dfs(pos+1,tleft-tcost[pos])+mget[pos]\ ,\ dfs(pos+1,tleft)

即为

mem[pos][tleft] = max(mem[pos+1][tleft-tcost[pos]]+mget[pos]\ ,\ mem[pos+1][tleft])

这不就是dp的状态转移?

总结一下：

记忆化搜索和动态规划从根本上来讲就是一个东西,**(印象中)任何一个 dp 方程都能转为记忆化搜索 ，反之亦然（为什么？见下文“体现在”的第四条）

体现在

建议好好想想第四条。记住，学一个算法，一定要理解他的精髓。

举个栗子:

dp[i][j][k] = dp[i+1][j+1][k-a[j]] + dp[i+1][j][k]

转为

int dfs( int i , int j , int k ){
    边界条件
    if( mem[i][j][k] != -1 ) return mem[i][j][k];
    return mem[i][j][k] = dfs(i+1,j+1,k-a[j]) + dfs(i+1,j,k);
}
int main(){
    memset(mem,-1,sizeof(mem));
    读入
    cout << dfs(1,0,0) << endl;
}

二者满足上面提到的所有关系

3. 如何写记忆化搜索

方法I（由动态规划开始思考）:

  1. 把这道题的dp状态和方程写出来
  2. 根据他们写出dfs函数
  3. 添加记忆化数组

举例:

转为 ```cpp int dfs( int i ){ if( mem[i] != -1 ) return mem[i]; int ret = 1; for( int j = 1 ; j < i ; j++ ) if( a[j] < a[i] ) ret = max(ret,dfs(j)+1); return mem[i] = ret; } int main(){ memset(mem,-1,sizeof(mem)); 读入 cout << dfs(n) << endl; } ``` ### 方法II（由暴搜开始思考）: 1. 写出这道题的暴搜程序(最好是dfs) 2. 将这个dfs改成"无需外部变量"的dfs 3. 添加记忆化数组 举例: 本文最开始介绍"什么是记忆化搜索"时举的"采药"那题的例子，就是典型的方法II --- ## 4. 记忆化搜索的优缺点 优点: - 记忆化搜索可以避免搜到无用状态, 特别是在有状态压缩时 举例: 给你一个有向图(注意不是完全图),经过每条边都有花费,求从点1出发,经过每个点**恰好一次**后的最小花费(最后不用回到起点),保证路径存在. dp状态很显然: 设 $dp[pos][mask]$ 表示身处在 $pos$ 处,走过 $mask$(mask为一个二进制数) 中的顶点后的最小花费 常规 $dp$ 的状态为 $O(n\cdot 2^n)$ , 转移复杂度(所有的加在一起)为 $O(m)

但是!如果我们用记忆化搜索,就可以避免到很多无用的状态,比如 pos 为起点却已经经过了 >1 个点的情况.

然后就 rk1 了

举例: 用常规 dp 写"合并石子"需要先枚举区间长度然后枚举起点,但记忆化搜索直接枚举断点(就是枚举当前区间由哪两个区间合并而成)然后递归下去就行

缺点:

5. 记忆化搜索的注意事项

6. 相关文章推荐

《挑战程序设计竞赛》(又名白书)，对动态规划的引入的那一章（它也是从暴搜开始讲起）

如有疑问或质疑, 请留下评论或私信我

questions are welcome