稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

记忆化搜索简介

记忆化搜索(Memorization Search),是指在做搜索过程中(比如DFS或者动态规划中)把重叠的子问题的解或者状态存储下来,以防止重复计算。最为常见的就是图搜索方法BFS和DFS时都要对已搜索过的节点进行标记以防止重复遍历,这就是一种记忆化搜索方法。再如动态规划的重复子问题,用数组进行缓存以防止重复计算,这也是一种记忆化搜索方法。

记忆化搜索

记忆化搜索是自上而下的优化过程,通常用于优化有递推关系的递归算式,比如一些重叠子问题,像爬楼梯或者Fibonacci数列问题,它们的求解是f(i)=f(i-1)+f(i-2),如果直接使用递归算式也能得到答案,但重复计算太多,因此可以递推过程中引入记忆化搜索,用额外的存储空间把已计算过的值缓存下来,然后递归过程中如果需要引用时,就直接引用不用再重复计算。

它与动态规划的区别就在于,记忆化搜索是自顶而下的,正面的调用递归关系,比较符合常规的思维模式。但动态规划一般是自下而上的逆向求解递推关系。比如像Fibonacci数列,递推关系是f(i)=f(i-1)+f(i-2),动态规划是要把i从0到n这样逆着递推出来。

但关键的地方都在于先找到状态转移方程(也即递推关系)。

记忆化搜索要选用状态转移方程所定义的参数作为参数,然后进行向下递归调用。

应用记忆化搜索时要注意缓存结果状态时,需要对状态进行定义,一般要分为三种状态:1)是未计算的状态,这个很关键,因为未计算就要先去计算,否则就可以直接返回结果;2)是非法解,也即是找不到合理的解时的状态,这个是非法解也是解的一种,并不是未计算;3)是合法解。

还需要注意状态的个数,状态一般用数组或者哈希表来呈现,还要注意它与参数之间的对应关系。

典型题目

题目 题解 说明
131. 分割回文串 题解
322. 零钱兑换 题解 典型的递推式记忆化搜索
题解
题解
题解
题解

参考资料

Comments