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

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

记忆化搜索原理详解

一、什么是记忆化搜索

记忆化搜索（Memoization Search）是一种通过记录已经遍历过的状态信息，从而避免对同一状态重复遍历的搜索算法。可以把它理解为带有“备忘录”的递归——递归每次返回的时候，将结果放到备忘录里；每次进入递归的时候，先看看备忘录里有没有当前状态，如果有就直接返回，不用再重复计算。

#mermaid-svg-7LEVt5dahOx1uSIl{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-7LEVt5dahOx1uSIl .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-7LEVt5dahOx1uSIl .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-7LEVt5dahOx1uSIl .error-icon{fill:#552222;}#mermaid-svg-7LEVt5dahOx1uSIl .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-7LEVt5dahOx1uSIl .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-7LEVt5dahOx1uSIl .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-7LEVt5dahOx1uSIl .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-7LEVt5dahOx1uSIl .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-7LEVt5dahOx1uSIl .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-7LEVt5dahOx1uSIl .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-7LEVt5dahOx1uSIl .marker{fill:#333333;stroke:#333333;}#mermaid-svg-7LEVt5dahOx1uSIl .marker.cross{stroke:#333333;}#mermaid-svg-7LEVt5dahOx1uSIl svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-7LEVt5dahOx1uSIl p{margin:0;}#mermaid-svg-7LEVt5dahOx1uSIl .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-7LEVt5dahOx1uSIl .cluster-label text{fill:#333;}#mermaid-svg-7LEVt5dahOx1uSIl .cluster-label span{color:#333;}#mermaid-svg-7LEVt5dahOx1uSIl .cluster-label span p{background-color:transparent;}#mermaid-svg-7LEVt5dahOx1uSIl .label text,#mermaid-svg-7LEVt5dahOx1uSIl span{fill:#333;color:#333;}#mermaid-svg-7LEVt5dahOx1uSIl .node rect,#mermaid-svg-7LEVt5dahOx1uSIl .node circle,#mermaid-svg-7LEVt5dahOx1uSIl .node ellipse,#mermaid-svg-7LEVt5dahOx1uSIl .node polygon,#mermaid-svg-7LEVt5dahOx1uSIl .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-7LEVt5dahOx1uSIl .rough-node .label text,#mermaid-svg-7LEVt5dahOx1uSIl .node .label text,#mermaid-svg-7LEVt5dahOx1uSIl .image-shape .label,#mermaid-svg-7LEVt5dahOx1uSIl .icon-shape .label{text-anchor:middle;}#mermaid-svg-7LEVt5dahOx1uSIl .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-7LEVt5dahOx1uSIl .rough-node .label,#mermaid-svg-7LEVt5dahOx1uSIl .node .label,#mermaid-svg-7LEVt5dahOx1uSIl .image-shape .label,#mermaid-svg-7LEVt5dahOx1uSIl .icon-shape .label{text-align:center;}#mermaid-svg-7LEVt5dahOx1uSIl .node.clickable{cursor:pointer;}#mermaid-svg-7LEVt5dahOx1uSIl .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-7LEVt5dahOx1uSIl .arrowheadPath{fill:#333333;}#mermaid-svg-7LEVt5dahOx1uSIl .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-7LEVt5dahOx1uSIl .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-7LEVt5dahOx1uSIl .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-7LEVt5dahOx1uSIl .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-7LEVt5dahOx1uSIl .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-7LEVt5dahOx1uSIl .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-7LEVt5dahOx1uSIl .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-7LEVt5dahOx1uSIl .cluster text{fill:#333;}#mermaid-svg-7LEVt5dahOx1uSIl .cluster span{color:#333;}#mermaid-svg-7LEVt5dahOx1uSIl div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-7LEVt5dahOx1uSIl .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-7LEVt5dahOx1uSIl rect.text{fill:none;stroke-width:0;}#mermaid-svg-7LEVt5dahOx1uSIl .icon-shape,#mermaid-svg-7LEVt5dahOx1uSIl .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-7LEVt5dahOx1uSIl .icon-shape p,#mermaid-svg-7LEVt5dahOx1uSIl .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-7LEVt5dahOx1uSIl .icon-shape .label rect,#mermaid-svg-7LEVt5dahOx1uSIl .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-7LEVt5dahOx1uSIl .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-7LEVt5dahOx1uSIl .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-7LEVt5dahOx1uSIl :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

有

没有

开始递归调用

备忘录中有当前状态吗?

直接返回备忘录中的值

进行递归/状态转移计算

将计算结果存入备忘录

返回计算结果

结束

二、核心原理

记忆化搜索能优化的问题必须满足两个条件：

记忆化搜索的本质是用空间换时间：第一次计算子问题时，将结果存入缓存；后续遇到相同子问题时，直接从缓存读取结果，无需重复递归。

三、 记忆化搜索 vs 传统DP

记忆化搜索算法上依然是搜索的流程，但搜索到的一些解用动态规划的思想和模式作保存。一般来说，动态规划需要遍历所有状态，而搜索可以排除一些无效状态。

四、 实现框架

#include<bits/stdc++.h>
using namespace std;

// 1. 定义备忘录数组（大小根据问题状态空间确定）
int f[N][M]; // f数组存储已经计算过的状态结果

// 2. DFS递归函数
int dfs(int i, int j) {
// 边界条件：递归终止条件
if (边界条件) return 边界值;

// 3. 查备忘录：如果当前状态已经计算过，直接返回
if (f[i][j] != –1) return f[i][j];

// 4. 状态转移：搜索所有可能的选择
int ans = 初始值;
for (所有可能的选择) {
ans = max(ans / min(ans) / ans + 子问题的结果);
}

// 5. 存备忘录：将结果存入备忘录后返回
return f[i][j] = ans;
}

int main() {
// 初始化备忘录为-1（表示未计算过）
memset(f, –1, sizeof(f));
// 调用DFS得到答案
cout << dfs(起始状态) << endl;
return 0;
}

实现记忆化搜索的关键是：按照“可变参数→返回值”的格式创建备忘录，可变参数通常对应DP中的状态维度，返回值对应答案。

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》： https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

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>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}