记忆化搜索（Memoization 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. 分割回文串 | 题解 | |
| 174. 地下城游戏 | 题解 | 搜索方向与常规方向相反 |
| 322. 零钱兑换 | 题解 | 典型的递推式记忆化搜索 |
| 312. 戳气球 | 题解 | 区间DP，二维记忆 |
| 474. 一和零 | 题解 | |
| 486. 预测赢家 | 题解 | |
| 509. 斐波那契数 | 题解 | 理解自底向上和自顶而下 |
| 787. K 站中转内最便宜的航班 | 题解 | |
| 983. 最低票价 | 题解 | |
| 2140. 解决智力问题 | 题解 | |
| 2466. 统计构造好字符串的方案数 | 题解 | |
| 3040. 相同分数的最大操作数目 II | 题解 | |
| 题解 | ||
| 题解 | ||
| 题解 | ||
| 题解 |
记忆化搜索的缺点
记忆化搜索通常作为递归重复子问题的优化，自顶而下比较符合直观的思维。
但记忆化搜索的空间复杂度较高，通过是参数的维度乘积，而且不像自下而上的递推式DP，可以复用数组滚动来优化空间，记忆化搜索空间无法优化。比如背包问题，用记忆化搜索空间复杂度始终是O(n2)，而如果用DP可以优化到O(n)。