C++记忆化搜索

记忆化搜索简介记忆化搜索Memoization Search是一种通过存储已经遍历过的状态信息从而避免对同一状态重复遍历的搜索算法。记忆化搜索是动态规划的一种实现方式。在记忆化搜索中当算法需要计算某个子问题的结果时它首先检查是否已经计算过该问题。如果已经计算过则直接返回已经存储的结果否则计算该问题并将结果存储下来以备将来使用。「记忆化搜索」与「递推」区别两者都是动态规划的实现方式区别如下。记忆化搜索「自顶向下」的解决问题采用自然的递归方式编写过程在过程中会保存每个子问题的解通常保存在一个数组或哈希表中来避免重复计算。优点代码清晰易懂可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题通过递归调用来解决。个人体会有时有大量非法状态记忆化搜索的时候会自动忽略。缺点可能会因为递归深度过大而导致栈溢出问题。递推「自底向上」的解决问题采用循环的方式编写过程在过程中通过保存每个子问题的解通常保存在一个数组或哈希表中来避免重复计算。优点避免了深度过大问题不存在栈溢出问题。计算顺序比较明确易于实现。缺点无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂如果使用递推方法来计算就会导致代码实现变得非常困难。场景适合使用「记忆化搜索」的场景问题的状态转移方程比较复杂递推关系不是很明确。问题适合转换为递归形式并且递归深度不会太深。适合使用「递推」的场景问题的状态转移方程比较简单递归关系比较明确。问题不太适合转换为递归形式或者递归深度过大容易导致栈溢出。记忆化搜索解题步骤我们在使用记忆化搜索解决问题的时候其基本步骤如下写出问题的动态规划「状态」和「状态转移方程」。定义一个缓存数组或哈希表用于保存子问题的解。定义一个递归函数用于解决问题。在递归函数中首先检查缓存中是否已经存在需要计算的结果如果存在则直接返回结果否则进行计算并将结果存储到缓存中再返回结果。在主函数中调用递归函数并返回结果。题目难度分【动态规划】【记忆化搜索】【回文】1312让字符串成为回文串的最少插入次数1786【记忆化搜索】【剪枝】【C算法】1553吃掉 N 个橘子的最少天数2048【记忆化搜索】2318. 不同骰子序列的数目2090【前缀和 记忆化搜索】LeetCode1444. 切披萨的方案数2126【记忆化搜索 】2312. 卖木头块2363【动态规划】【记忆化搜索】【状态压缩】1681. 最小不兼容性2389【数学】【记忆化搜索 】【动态规划】964. 表示数字的最少运算符2594【动态规划】【记忆化搜索】C算法546移除盒子【动态规划】【记忆化搜索】【C算法】664. 奇怪的打印机扩展阅读算法为骨CAD为魂亲士工具箱支持中望CAD2024、AutoCad2013及以上多年承接CAD项目的精华工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。