信奥赛C++提高组csp-s之搜索进阶（记忆化搜索核心思想）

信奥赛C提高组csp-s之搜索进阶记忆化搜索核心思想记忆化搜索原理详解一、什么是记忆化搜索记忆化搜索Memoization Search是一种通过记录已经遍历过的状态信息从而避免对同一状态重复遍历的搜索算法。可以把它理解为带有“备忘录”的递归——递归每次返回的时候将结果放到备忘录里每次进入递归的时候先看看备忘录里有没有当前状态如果有就直接返回不用再重复计算。有没有开始递归调用备忘录中有当前状态吗?直接返回备忘录中的值进行递归/状态转移计算将计算结果存入备忘录返回计算结果结束二、核心原理记忆化搜索能优化的问题必须满足两个条件重叠子问题不同的递归路径会重复计算同一个子问题如斐波那契数列中f(5)需要f(4)和f(3)f(4)又需要f(3)和f(2)f(3)被重复计算多次最优子结构一个问题的最优解可以由其子问题的最优解推导而来记忆化搜索的本质是用空间换时间第一次计算子问题时将结果存入缓存后续遇到相同子问题时直接从缓存读取结果无需重复递归。三、 记忆化搜索 vs 传统DP维度记忆化搜索DFS缓存传统DP迭代实现方式递归代码简洁符合直觉迭代需手动规划状态转移顺序适用场景状态转移复杂如区间DP、树形DP状态转移简单如线性DP空间开销额外递归栈开销无递归栈开销计算方式按需计算只算需要的子问题按顺序计算可能算无用子问题记忆化搜索算法上依然是搜索的流程但搜索到的一些解用动态规划的思想和模式作保存。一般来说动态规划需要遍历所有状态而搜索可以排除一些无效状态。四、 实现框架#includebits/stdc.husingnamespacestd;// 1. 定义备忘录数组大小根据问题状态空间确定intf[N][M];// f数组存储已经计算过的状态结果// 2. DFS递归函数intdfs(inti,intj){// 边界条件递归终止条件if(边界条件)return边界值;// 3. 查备忘录如果当前状态已经计算过直接返回if(f[i][j]!-1)returnf[i][j];// 4. 状态转移搜索所有可能的选择intans初始值;for(所有可能的选择){ansmax(ans/min(ans)/ans子问题的结果);}// 5. 存备忘录将结果存入备忘录后返回returnf[i][j]ans;}intmain(){// 初始化备忘录为-1表示未计算过memset(f,-1,sizeof(f));// 调用DFS得到答案coutdfs(起始状态)endl;return0;}实现记忆化搜索的关键是按照“可变参数→返回值”的格式创建备忘录可变参数通常对应DP中的状态维度返回值对应答案。更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}