引言下半年各类信息学相关认证与活动陆续进入冲刺期在初赛「阅读程序 / 完善程序」以及复赛上机题型里动态规划含记忆化搜索始终是出现频率最高的核心考点之一。很多同学一看到递推就头大其实只要把「递归 缓存」这套思路吃透一大类「从某点出发、按规则走到最优」的题都能迎刃而解。本文用一个经典的「滑雪 / 山谷滑行」模型带你彻底搞懂记忆化搜索自顶向下动态规划为什么它能把指数级暴力压成线性状态该怎么定义记忆数组怎么用以及几个常踩的坑。文末还给出可落地的进阶方向。建议边读边敲。所有代码均给出 C 与 Python 双版本可直接复制到本地运行。题目山谷最长滑行路线【题目描述】给定一个 R 行 C 列的山谷高度矩阵 H每个格子有一个整数高度。小探险家可以从任意一个格子出发每一步只能向上下左右四个相邻格子移动且必须移动到严格更低的格子。求从任意起点出发能经过的最多格子数即最长滑行路线的长度含起点本身。【输入格式】第一行两个整数 R、C1 ≤ R, C ≤ 100。接下来 R 行每行 C 个整数表示高度矩阵 H0 ≤ H[i][j] ≤ 10000。【输出格式】一个整数表示最长滑行路线经过的格子数。【样例输入】3 3 1 2 3 6 5 4 7 8 9【样例输出】9【样例解释】从高度为 9 的格子出发9 → 8 → 7 → 6 → 5 → 4 → 3 → 2 → 1共经过 9 个格子每一步都向严格更低的相邻格子移动且用完了全部 9 个格子因此无法更长。核心考点状态定义f(i, j)表示从格子(i, j)出发能滑行的最长长度。递归转移f(i, j) 1 max{ f(nr, nc) | 相邻且 H[nr][nc] H[i][j] }没有更低邻居时f(i, j) 1。记忆化缓存同一个格子可能被多个方向反复到达缓存算过的结果避免重复计算。全局答案枚举所有起点ans max f(i, j)。边界与合法性越界判断、严格递减判断、记忆数组初始化。复杂度每个格子只算一次状态数 O(RC)单状态转移 O(4)整体 O(RC)。与递推的关系记忆化是自顶向下递归的 DP理解后能自然过渡到自底向上的循环写法。解法与拆解思路拆解最直接的想法是从每个格子出发枚举所有合法下滑路径取最长。但这样会重复搜索大量子路径复杂度指数级爆炸。关键观察「从 A 出发的最长滑行长度」只取决于 A 及其下方子问题与「是怎么走到 A 的」无关」。这就是最优子结构。于是我们用一个memo[i][j]记录已算出的f(i, j)- 计算前先看memo[i][j]是否已算过算过直接返回- 没算过就递归求四周更低格子的结果取最大值 1再写回memo[i][j]。这叫记忆化搜索本质上和动态规划等价只是用递归来表达写起来更贴合「从某点出发」的题意。C 实现#include iostream #include vector #include algorithm using namespace std; int R, C; vectorvectorint H; vectorvectorint memo; // 四个方向上、下、左、右 int dirs[4][2] { {-1,0}, {1,0}, {0,-1}, {0,1} }; int dfs(int r, int c) { if (memo[r][c] ! -1) return memo[r][c]; // 已算过直接返回 int best 1; // 至少包含自己这一个格子 for (auto d : dirs) { int nr r d[0], nc c d[1]; if (nr 0 nr R nc 0 nc C H[nr][nc] H[r][c]) { best max(best, 1 dfs(nr, nc)); // 严格更低才能滑过去 } } return memo[r][c] best; // 写回记忆数组 } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); if (!(cin R C)) return 0; H.assign(R, vectorint(C)); memo.assign(R, vectorint(C, -1)); // 初始化为 -1 表示「未计算」 for (int i 0; i R; i) for (int j 0; j C; j) cin H[i][j]; int ans 0; for (int i 0; i R; i) for (int j 0; j C; j) ans max(ans, dfs(i, j)); // 枚举所有起点取最大 cout ans \n; return 0; }Python 实现import sys sys.setrecursionlimit(1000000) # 递归深度可能较大显式放大 def solve(): data sys.stdin.read().strip().split() if not data: return it iter(data) R int(next(it)); C int(next(it)) H [[int(next(it)) for _ in range(C)] for _ in range(R)] memo [[-1] * C for _ in range(R)] # -1 表示「未计算」 dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(r, c): if memo[r][c] ! -1: return memo[r][c] best 1 for dr, dc in dirs: nr, nc r dr, c dc if 0 nr R and 0 nc C and H[nr][nc] H[r][c]: best max(best, 1 dfs(nr, nc)) memo[r][c] best return best ans 0 for i in range(R): for j in range(C): ans max(ans, dfs(i, j)) print(ans) if __name__ __main__: solve()两份代码逻辑完全一致用memo把O(4^RC)的暴力剪成了O(RC)。样例3×3矩阵输出正是9。易错点提醒严格递减别写成 ≤题目是「更低」用而非用错会死循环或算错。记忆数组初值必须用-1或「不可能出现的答案值」表示「未计算」若初始化成 0会和「真实答案 0」混淆导致误判已算过。先查缓存再递归漏掉if memo ! -1 return就退化成纯暴力大数据直接超时。递归返回前写回写成return max(...)却忘了赋值给memo[r][c]等于没记忆。Python 递归深度网格较大时默认递归上限1000不够务必setrecursionlimit。全局最大值取错位置答案是所有起点的f(i,j)最大值不是从固定(0,0)出发的值。进阶方向路径计数把「最长长度」改成「长度为最长的路径有多少条」记忆数组存(长度, 方案数)二元组转移时按长度合并方案数。路径还原记录每个状态「下一步走向哪个邻居最优」从全局最优起点回溯打印具体路线。改成自底向上 DP拓扑排序按高度升序处理dp[x]由所有比它高的邻居更新循环写法更省栈空间适合超大规模网格。与图论结合把「高度严格递减」看成有向无环图DAG上的最长路记忆化搜索本质上就是 DAG 上 DFS 求最长路可类比到任务依赖、表达式求值等场景。小结与互动记忆化搜索 递归定义子问题 用数组缓存结果是动态规划最易上手的一种写法。今天这道题的口诀是状态f(i,j) 从(i,j)出发的最长滑行四周更低则1 f(邻居)算过就存别重复算。把这套「定义状态 → 写递归 → 加缓存」的流程练熟你就能拿下信息学测评里一大类「最长 / 最多 / 最优路径」题型。互动时间你在练习中还遇到过哪些「看起来像搜索、其实该用记忆化」的题欢迎在评论区留言下一篇我们可以聊聊记忆化如何过渡到自底向上递推的写法。如果本文对你有帮助别忘了点赞收藏关注获取每日算法精讲。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。