记忆化搜索汇总
记忆化搜索简介
记忆化搜索（Memoization Search）：是一种通过存储已经遍历过的状态信息，从而避免对同一状态重复遍历的搜索算法。
记忆化搜索是动态规划的一种实现方式。在记忆化搜索中，当算法需要计算某个子问题的结果时，它首先检查是否已经计算过该问题。如果已经计算过，则直接返回已经存储的结果；否则，计算该问题，并将结果存储下来以备将来使用。
「记忆化搜索」与「递推」区别
两者都是动态规划的实现方式，区别如下。
记忆化搜索
「自顶向下」的解决问题，采用自然的递归方式编写过程，在过程中会保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
优点：代码清晰易懂，可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的，使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题，通过递归调用来解决。
个人体会：有时有大量非法状态，记忆化搜索的时候会自动忽略。
缺点：可能会因为递归深度过大而导致栈溢出问题。
递推
「自底向上」的解决问题，采用循环的方式编写过程，在过程中通过保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
优点：避免了深度过大问题，不存在栈溢出问题。计算顺序比较明确，易于实现。
缺点：无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂，如果使用递推方法来计算，就会导致代码实现变得非常困难。
场景
适合使用「记忆化搜索」的场景：
问题的状态转移方程比较复杂，递推关系不是很明确。
问题适合转换为递归形式，并且递归深度不会太深。
适合使用「递推」的场景：
问题的状态转移方程比较简单，递归关系比较明确。
问题不太适合转换为递归形式，或者递归深度过大容易导致栈溢出。
记忆化搜索解题步骤
我们在使用记忆化搜索解决问题的时候，其基本步骤如下：
写出问题的动态规划「状态」和「状态转移方程」。
定义一个缓存（数组或哈希表），用于保存子问题的解。
定义一个递归函数，用于解决问题。在递归函数中，首先检查缓存中是否已经存在需要计算的结果，如果存在则直接返回结果，否则进行计算，并将结果存储到缓存中，再返回结果。
在主函数中，调用递归函数并返回结果。
题目
| 难度分 | |
|---|---|
| 【动态规划】【记忆化搜索】【回文】1312让字符串成为回文串的最少插入次数 | 1786 |
| 【记忆化搜索】【剪枝】【C++算法】1553吃掉 N 个橘子的最少天数 | 2048 |
| 【记忆化搜索】2318. 不同骰子序列的数目 | 2090 |
| 【前缀和 记忆化搜索】LeetCode1444. 切披萨的方案数 | 2126 |
| 【记忆化搜索 】2312. 卖木头块 | 2363 |
| 【动态规划】【记忆化搜索】【状态压缩】1681. 最小不兼容性 | 2389 |
| 【数学】【记忆化搜索 】【动态规划】964. 表示数字的最少运算符 | 2594 |
| 【动态规划】【记忆化搜索】C++算法：546移除盒子 | |
| 【动态规划】【记忆化搜索】【C++算法】664. 奇怪的打印机 |
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
