信息学奥赛的学习路线里，有一道题你迟早会撞上：信息学奥赛一本通 1280：【例9.24】滑雪、OpenJudge NOI 2.6 90:滑雪、洛谷 P1434 [SHOI2002] 滑雪。三个平台收录同一个题目，名字和样例一模一样，这在OJ圈里不算常见，也从侧面说明它是公认的入门必刷题。无论是准备CSP-J/S，还是刚开始接触算法竞赛，这道滑雪题都是绕不开的坎。
这道题表面是爬山滑雪的场景题，核心考的却是记忆化搜索（Memoization DFS）和动态规划的结合。很多初学者在DFS、BFS、DP之间来回切换时容易懵，而滑雪题恰好是打通“搜索 + 缓存 + 状态转移”这三堵墙的一把钥匙。刷透它，后面再碰最短路、拓扑序DP、区间DP这些内容时，你会发现自己对“状态”和“无后效性”的理解会明显上了一个台阶。
这篇文章我就按自己的刷题习惯，从题意、算法选型、代码实现、常见坑、延伸题目五个角度，把这道题完整拆开讲一遍。代码以C++为主，同时给一份Python参考版本，两者在三个平台上都可以直接提交通过。
1. 题目到底在说什么：看似简单，处处是坑
1.1 题意速览
给定一个 R 行 C 列的矩阵，每个格子里有一个数字表示高度。你从任意一个格子出发，每一步可以滑向上下左右四个方向中高度严格更低的格子。题目问你：按照这个规则，最长能滑多少步？
注意几个关键词：
- 起点任意，终点也任意，没有固定路径。
- 滑动方向只有上下左右四个，不能斜着滑。
- 目标格子的高度必须严格小于当前格子高度，等于都不行。
- 求的是路径上的格子数量，而不是移动的步数。走 1 条边算路径长度为 2。
这个“路径长度 = 格子数”的细节，经常有人弄错。比如样例输出是 25，指的就是一条包含 25 个格子的路径。
1.2 经典样例手推
样例输入是：
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9这个矩阵其实是一个从外圈到内圈的螺旋排列。数值 25 在矩阵正中央，数值 1 在左上角。最长路径可以从 25 出发，一路沿着 24、23、22……这样严格递减的顺序滑到 1，路径长度正好是 25。
如果没看明白，可以随便挑一个格子试一下：从 24 出发只能滑向 23、20、15、25 中比它小的格子，选择 23 之后继续往下滑。这就是一个典型的 DAG（有向无环图）上的最长路径问题。
1.3 为什么不能用裸DFS硬搜
刚拿到题，很多人第一反应是：从每个格子出发DFS，记录全局最大值。这个思路方向是对的，但实现上如果不加缓存，复杂度会非常难看。
最坏情况下，假设 R = C = 100，矩阵中有 10000 个格子。从每个格子出发都暴力DFS一次，每个DFS最多可能遍历几乎所有格子。直接写裸搜索，最坏时间复杂度是 O((R·C)²) 量级，也就是大约 10^8 次操作级别，在OJ上很容易超时。
那是不是该用BFS？BFS求的是最短路径，这里要的是最长路径，而且边权都是1，BFS并不适合直接求DAG上的最长路。所以我们需要换一个思路。
2. 核心算法思路：记忆化搜索为什么能一刀秒掉
2.1 找到重叠子问题
仔细观察DFS的过程，你会发现大量重复计算。举个例子：从格子 (2,3) 出发，如果它周围有多个方向可以走，那么它可能会被路径 A 访问一次，又被路径 B 访问一次。每当它被访问时，如果没有缓存，它又要把自己下游的所有路径重新算一遍，这就造成了指数级的浪费。
换个角度想：从任意格子 (i, j) 出发能滑出的最长长度，其实是一个固定值，和“我是从哪个格子滑到这里的”完全无关。这个性质在算法竞赛里有个专业名词，叫无后效性。既然这个值是固定的，那就把它存下来，下次再用到时直接查表。
这就是记忆化搜索，也叫带备忘录的DFS。它本质上就是动态规划的一种自顶向下实现方式。
2.2 状态定义和转移方程
定义一个二维数组 dp[i][j] 表示：从格子 (i, j) 出发，能滑出的最长路径长度（包括当前格子）。
转移方程很容易写：
dp[i][j] = 1 + max(dp[ni][nj])其中 (ni, nj) 是 (i, j) 上下左右四个方向中，高度严格小于 h[i][j] 的相邻格子。如果四个方向都没有可滑的格子，那么 dp[i][j] = 1，表示只能站在当前格子上。
这个方程的逻辑很直观：当前格子算 1 个，下一步选择四个方向里最长的那条路径继续滑。
最终的答案就是所有 dp[i][j] 的最大值。
2.3 递归过程如何避免死循环
因为转移条件是“高度严格小于”，所以从某个格子出发，永远不可能回到自己。也就是说，状态转移图是严格有向无环的。递归调用时不需要担心 A 调用 B、B 又回调 A 的情况。这一点是记忆化搜索能直接写的关键前提。
如果题目把“严格小于”改成“小于等于”，那么同样高度的格子之间互相转移就会成环，记忆化搜索就不能直接用了，必须先拓扑排序或做环检测。好在滑雪题的原始设定是严格递减，省了很多麻烦。
2.4 另一种正解：按高度排序 + DP
记忆化搜索是自顶向下的写法。还有一种自底向上的写法，也很经典：
把所有格子按高度从大到小排序，然后从高度大的格子开始，依次尝试用当前格子去更新它四周高度更小的格子。更新公式是：
dp[低处格子] = max(dp[低处格子], dp[当前格子] + 1)因为高度大的格子先处理，所以处理到任意一个格子时，所有能从它滑到的更低格子都已经有了最终的 dp 值。这就是一种拓扑顺序，保证每个格子最多被更新固定次数。
这种写法的好处是不用递归，也没有栈溢出的风险，但需要先做一次排序。在 R、C 不超过 100 的数据范围下，排序开销基本可以忽略。两种写法最终都能通过，下面我会给出记忆化搜索版本的完整代码，因为它的代码更短，也更容易理解。
3. 完整代码实现与关键细节
3.1 C++ 标准答案（记忆化搜索版）
#include <iostream> #include <algorithm> using namespace std; const int MAXN = 105; int r, c; int h[MAXN][MAXN]; int dp[MAXN][MAXN]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int dfs(int x, int y) { if (dp[x][y] != 0) { return dp[x][y]; } dp[x][y] = 1; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 1 && nx <= r && ny >= 1 && ny <= c && h[nx][ny] < h[x][y]) { dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1); } } return dp[x][y]; } int main() { cin >> r >> c; for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { cin >> h[i][j]; } } int ans = 0; for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { ans = max(ans, dfs(i, j)); } } cout << ans << endl; return 0; }我用下标 1 到 r、1 到 c 来存矩阵，好处是边界判断可以统一写成nx >= 1 && nx <= r这种形式，不容易越界。dp 数组初始化为 0，0 表示“还没计算过”，因为任意一个格子至少能贡献长度 1，所以计算过的 dp 值至少为 1，不会和 0 混淆。
3.2 核心逻辑逐段拆解
递归函数dfs(x, y)是本代码的灵魂部分。进入函数后，先检查dp[x][y]是否已经计算过，如果算过就直接返回，这就是记忆化的核心操作，也是省时间的根本原因。
然后默认赋值dp[x][y] = 1，表示当前格子本身算一步。接着遍历四个方向，对每个满足“在矩阵内且高度更低”的格子，递归调用dfs(nx, ny)，再用“下游路径 + 1”来更新当前格子的最长值。
主函数里的双重循环负责枚举起点。因为起点是任意的，所以需要对所有格子都调用一次dfs，但由于记忆化的存在，每个格子最多被真正计算一次，之后的所有访问都是 O(1) 的查表。
3.3 关于初始化的两种写法和一个陷阱
有些教材里把 dp 初始化为 -1，然后判断dp[x][y] != -1来作为“已计算”的标记。这种写法也可以，但要注意：如果你直接把 dp 初值设为 0，却在 dfs 里先判断if (dp[x][y]) return dp[x][y];，然后不先赋 1 就直接枚举，那么当前格子无法滑动时，返回的可能是 0，最终答案就会少算。这个细节非常坑，我见过不少人在这种写法上翻车。
我自己的习惯是：dp 数组清 0，进入 dfs 后先赋 1，再判断是否更新。这样逻辑最清晰，也不容易出错。
3.4 Python 版本参考
如果你主要在洛谷或 OpenJudge 上用 Python 刷题，可以参考下面这份代码：
import sys sys.setrecursionlimit(1000000) r, c = map(int, input().split()) h = [list(map(int, input().split())) for _ in range(r)] dp = [[0] * c for _ in range(r)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def dfs(x, y): if dp[x][y]: return dp[x][y] dp[x][y] = 1 for k in range(4): nx = x + dx[k] ny = y + dy[k] if 0 <= nx < r and 0 <= ny < c and h[nx][ny] < h[x][y]: dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1) return dp[x][y] ans = 0 for i in range(r): for j in range(c): ans = max(ans, dfs(i, j)) print(ans)Python 版本把矩阵下标改成从 0 开始，和 C++ 版本下标从 1 开始有所不同，但思路完全一样。需要注意：Python 默认递归深度只有 1000，而这道题的最长路径极端情况下可以达到 R·C，也就是最多 10000，所以必须设置sys.setrecursionlimit，否则会报 RecursionError。
3.5 极端数据下的递归深度问题
说到递归深度，C++ 一般不用担心，因为默认栈空间通常足够支撑上万层的递归调用。但个别OJ的栈空间设置比较小，如果你遇到莫名奇妙的“段错误”，又确定算法没错，可以想想是不是递归深度过大。
如果你实在担心，可以改用排序 + DP 的递推写法，彻底避免递归。递推版本的核心代码如下：
struct Node { int x, y, val; } nodes[MAXN * MAXN]; bool cmp(Node a, Node b) { return a.val > b.val; } // 将所有点存进 nodes 数组并按高度从大到小排序 sort(nodes, nodes + cnt, cmp); for (int k = 0; k < cnt; k++) { int x = nodes[k].x; int y = nodes[k].y; for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx >= 1 && nx <= r && ny >= 1 && ny <= c && h[nx][ny] < h[x][y]) { dp[nx][ny] = max(dp[nx][ny], dp[x][y] + 1); } } }这种写法把“从高往低推”的过程显式化，代码写起来稍长一点，但稳定性更高，也更容易向别人解释状态转移的过程。
4. 常见错误与排查技巧实录
4.1 高频错误速查表
| 错误类型 | 典型表现 | 原因 | 解决办法 |
|---|---|---|---|
| 边界判断写反 | 数组越界或漏算边缘格子 | 行列下标搞混，或忘了判断 nx >= 1 | 统一用 1 下标，先判断范围再访问 |
| 高度关系写反 | 结果变短或答案错误 | 把 h[nx][ny] < h[x][y] 写成大于 | 记住“滑向更低处”这个常识 |
| 记忆化初始值设错 | 答案总是少 1 | dp 初值不区分未计算和合法值 | 用 0 标记未计算，入口先赋 1 |
| 递归深度爆炸 | Python 报 RecursionError | 未设置递归上限 | 加 sys.setrecursionlimit |
| 多重循环方向搞混 | 输入读取错乱 | R 和 C 的位置交换 | 先读 R 再读 C，逐行读入 |
| 忘记取最大值 | 输出每个起点的某个局部答案 | 主函数只调用一次 dfs | 双重循环里 ans = max(ans, ...) |
这张表里的问题，特别是前三条，是初学者报错的重灾区。如果你提交后答案错误，先按表里这几项排查，大概率能很快发现问题。
4.2 最容易踩的坑：严格递减千万不能写成小于等于
题目说的是高度严格更低的格子才能滑，也就是相邻格子的高度必须满足h[相邻] < h[当前]。如果把条件写成<=，在存在等高的矩阵里，两条路径会互相依赖，形成一个逻辑上的“环”，记忆化搜索的结果就会错乱。
可能有人会想：测试数据里会不会没有等高的情况？那也不行。竞赛题目的数据范围从不说死，你永远不知道评测数据长什么样。规范的做法是严格按题目要求实现，而不是赌数据。
我在最开始写这题时，就因为在调试时随手把<改成了<=去做测试，结果答案怎么都不对。排查了很久才发现是这个问题。从那以后，我每次看题都会先把“严格”这两个字圈出来。
4.3 边界条件的三种处理风格
处理矩阵边界有三种常见风格：
- 下标从 1 开始，判断
nx >= 1 && nx <= r，这是我给的 C++ 代码的风格。 - 下标从 0 开始，判断
nx >= 0 && nx < r，这是 Python 代码的风格。 - 在矩阵外面围一圈高度为无穷大的哨兵，这样越界访问自动被高度条件拦截。
三种风格没有绝对的好坏，关键是统一。最怕的是混用：一会儿从 0 开始，一会儿从 1 开始，自己写high了，最后边界判断就乱了。
我个人推荐比赛时用第一种或第二种，因为围哨兵虽然写起来省事，但需要额外初始化一圈数组，稍有不慎反而容易出错。
4.4 如何快速定位递归答案的错位
如果答案不对，又不想从头看代码，我有个很实用的调试方法：把 dp 数组打印出来，对比几个关键格子的预期值。
对于上面的样例，打印出来的 dp 数组应该呈现一种规律：边缘格子的 dp 值较小，中心附近格子的 dp 值较大，最大值出现在高度 25 那个位置。如果某个格子的 dp 值和附近格子的关系明显不协调，说明那一片的转移逻辑可能写错了。
这个方法比单步调试快得多。尤其是矩阵数据规模比较大的时候，肉眼扫一遍 dp 表，往往一眼就能看出问题在哪里。
4.5 提交环境的差异与平台选择
信息学奥赛一本通、OpenJudge、洛谷三个平台的编译器版本略有差异。OpenJudge 的 NOI 系列题目支持 C++，老版本对 C++11 及以上特性的支持可能不够完善，所以提交前最好别用auto、基于范围的for循环等新特性。洛谷对 C++14、C++17 的支持比较友好，大部分现代语法都能用。
如果你在 OpenJudge 上编译失败，最稳妥的办法就是把代码改成纯 C++98 风格：变量统一在函数开头声明，不使用auto，流输入输出用iostream即可。
5. 从滑雪题延伸出去：同类题目与进阶方向
5.1 为什么说它是“最值得背的模板题之一”
滑雪题的精髓在于：它把一个看起来需要暴力搜索的问题，通过“状态缓存”的方式优化成了近似 O(R·C) 的线性问题。这个思路在算法竞赛里适用性极广。
很多题目表面上是搜索题，但如果你在搜索中发现了重叠子问题，就应该立刻想起记忆化搜索。比如经典的斐波那契数列、方格取数、数字三角形、最长上升子序列，都可以用这个思路统一理解。滑雪题恰好是这些题目中最具“场景感”的一个，形象好记，代码又短，所以被无数教练当作课堂例题。
5.2 适合接着做的同类题目
- 洛谷 P1216 [USACO1.5][IOI1994] 数字三角形：入门级DP，从底向上推，和滑雪题的转移思想一致。
- 洛谷 P4017 最大食物链计数：拓扑序DP，和滑雪题的“排序 + DP”写法有异曲同工之妙。
- 洛谷 P2196 挖地雷：经典记忆化搜索/DP题，同样是DAG上的最长路径。
- 洛谷 P3183 食物链：NOI题，需要先建图做拓扑排序，再DP。
- POJ 1088 滑雪：这道题的原始来源之一，和 P1434 几乎一样，适合拿去练英文题面阅读。
把这些题目按顺序刷一遍，你对记忆化搜索和DAG上DP的理解会非常扎实。
5.3 我的一点刷题心得
这道题我前前后后至少刷过五遍。第一遍是刚学DFS时写的裸暴力，超时；第二遍学会了记忆化，AC了；第三遍是在学拓扑排序后，用“排序 + DP”重新写了一遍；第四遍是在学Python时又写了一个版本；第五遍是带学生时专门准备课件，把每个细节又抠了一遍。
每一遍都有新的收获。这可能就是经典题的意义：它不仅是一道题，更是一把尺子，量出你每个阶段对算法理解的深度。
如果你现在正卡在这个题上，别急。先用自己的话把状态定义说清楚，再动手写递归，写完再试着把递归改成递推。这个过程走完，你收获的绝对不止一个 AC。
