信奥赛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） |
| 空间开销 | 额外递归栈开销 | 无递归栈开销 |
| 计算方式 | 按需计算（只算需要的子问题） | 按顺序计算（可能算无用子问题） |
记忆化搜索算法上依然是搜索的流程，但搜索到的一些解用动态规划的思想和模式作保存。一般来说，动态规划需要遍历所有状态，而搜索可以排除一些无效状态。
四、 实现框架
#include<bits/stdc++.h>usingnamespacestd;// 1. 定义备忘录数组（大小根据问题状态空间确定）intf[N][M];// f数组存储已经计算过的状态结果// 2. DFS递归函数intdfs(inti,intj){// 边界条件：递归终止条件if(边界条件)return边界值;// 3. 查备忘录：如果当前状态已经计算过，直接返回if(f[i][j]!=-1)returnf[i][j];// 4. 状态转移：搜索所有可能的选择intans=初始值;for(所有可能的选择){ans=max(ans/min(ans)/ans+子问题的结果);}// 5. 存备忘录：将结果存入备忘录后返回returnf[i][j]=ans;}intmain(){// 初始化备忘录为-1（表示未计算过）memset(f,-1,sizeof(f));// 调用DFS得到答案cout<<dfs(起始状态)<<endl;return0;}实现记忆化搜索的关键是：按照“可变参数→返回值”的格式创建备忘录，可变参数通常对应DP中的状态维度，返回值对应答案。
更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
3、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.html
4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
