深搜骗分
DP 类路径问题骗分
作为一个广受赞扬的骗分算法,$DFS$ 的作用在解决不少 $Dp$问题 上尤为显著。
不过,深搜不能很好的处理重叠子问题,所以导致效率太低,
动态规划虽然比较好地处理了重叠子问题,但是在有些拓扑关系比较复杂的题目面前,又显得无奈。
记忆化搜索正是在这样的情况下产生的,它采用 搜索的形式 和 动态规划中递推的思想
将这两种方法有机地综合在一起,扬长避短,简单实用,在信息学中有着重要的作用。
记忆化搜索 = 搜索的形式 + 动态规划的思想。
1.记忆化搜索的思想
记忆化搜索的思想是,在搜索过程中,会有很多重复计算,如果我们能记录一些状态的答案,就可以减少重复搜索量
2、记忆化搜索的适用范围
根据记忆化搜索的思想,它是解决重复计算,而不是重复生成,
也就是说,这些搜索必须是在搜索扩展路径的过程中分步计算的题目,也就是“搜索答案与路径相关”的题目,而不能是搜索一个路径之后才能进行计算的题目,
必须要分步计算,并且搜索过程中,一个搜索结果必须可以建立在同类型问题的结果上,也就是类似于动态规划解决的那种。
也就是说,他的问题表达,不是单纯生成一个走步方案,而是生成一个走步方案的代价等,而且每走一步,在搜索树/图中生成一个新状态,都可以精确计算出到此为止的费用,
也就是,可以分步计算,这样才可以套用已经得到的答案
3、记忆化搜索的核心实现
a. 首先,要通过一个表记录已经存储下的搜索结果,一般用哈希表实现
b.状态表示,由于是要用哈希表实现,所以状态最好可以用数字表示,常用的方法是把一个状态连写成一个p进制数字,然后把这个数字对应的十进制数字作为状态
c.在每一状态搜索的开始,高效的使用哈希表搜索这个状态是否出现过,如果已经做过,直接调用答案,回溯
d.如果没有,则按正常方法搜索
4、记忆化搜索是类似于动态规划的,不同的是,它是倒做的“递归式动态规划”。
例题
虽然记搜很有用,但本质上也是运用 $Dp$的知识点,所以万不可盲目判断,分析后在动手,是最重要的。
先看例题:
简述:给定一个方格矩阵,每个方格内都有数字,可往上下右三方向扩展,一方格只能经过一次。
求,可以从左上角走到右下角的路径和最大是多少。
这是一道经典题的扩展,具体分析步骤如下。