记忆化搜索
记忆化搜索是啥：
-
不依赖任何 外部变量
-
答案以返回值的形式存在, 而不能以参数的形式存在(就是不能将
dfs定义成dfs(pos,tleft,nowans), 这里面的nowans不符合要求). -
对于相同一组参数,
dfs返回值总是相同的
说白了，记忆化搜索就等于动态规划，只不过换了种方式写罢了。
那么怎么写记忆化搜索捏？
方法一：
- 把这道题的
dp状态和方程写出来 - 根据他们写出
dfs函数 - 添加记忆化数组
就比如你写最长上升子序列，推出来 \(dp[i] = max\{dp[j]+1\}\quad 1 \leq j < i \text{且}a[j]<a[i]\)
然后就可以写记忆化了。
方法二：
- 写出这道题的暴搜程序(最好是
dfs) - 将这个
dfs改成"无需外部变量"的dfs - 添加记忆化数组
这两种方法都挺常用的，按照实际情况来吧。
记忆化搜索的优缺点：
优点：
- 记忆化搜索可以避免搜到无用状态, 特别是在有状态压缩时。
举例: 给你一个有向图(注意不是完全图),经过每条边都有花费,求从点 \(1\) 出发,经过每个点恰好一次后的最小花费(最后不用回到起点),保证路径存在。
dp状态很显然：
设 \(dp[pos][mask]\) 表示身处在 \(pos\) 处,走过 \(mask\)(mask为一个二进制数) 中的顶点后的最小花费。
常规 \(dp\) 的状态为 \(O(n\cdot 2^n)\) , 转移复杂度(所有的加在一起)为 \(O(m)\)
但是！如果我们用记忆化搜索,就可以避免到很多无用的状态,比如 \(pos\) 为起点却已经经过了 \(>1\) 个点的情况。
- 不需要注意转移顺序(这里的"转移顺序"指正常dp中for循环的嵌套顺序以及循环变量是递增还是递减)。
举例： 用常规 dp 写"合并石子"需要先枚举区间长度然后枚举起点,但记忆化搜索直接枚举断点(就是枚举当前区间由哪两个区间合并而成)然后递归下去就行。
-
边界情况非常好处理, 且能有效防止数组访问越界。
-
写起来简单易懂。 -
有些
dp(如区间dp)用记忆化搜索写很简单但正常dp很难。 -
记忆化搜索天生携带搜索天赋,可以使用技能"剪枝"。
缺点：
- 致命伤: 不能滚动数组。
- 有些优化比较难加。
- 由于递归, 有时效率较低但不至于
TLE(状压dp除外)。
记忆化搜索的注意事项：
- 别忘了加记忆化。
- 边界条件要加在检查当前数组值是否为 - 1 前(防止越界)
- 数组不要开小了（
- 在某些时候需要优化（如滚动数组、斜率优化时还是要用正常的
dp。