信息学奥赛的学习路线里有一道题你迟早会撞上信息学奥赛一本通 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上很容易超时。那是不是该用BFSBFS求的是最短路径这里要的是最长路径而且边权都是1BFS并不适合直接求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 数组初始化为 00 表示“还没计算过”因为任意一个格子至少能贡献长度 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] 写成大于记住“滑向更低处”这个常识记忆化初始值设错答案总是少 1dp 初值不区分未计算和合法值用 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老版本对 C11 及以上特性的支持可能不够完善所以提交前最好别用auto、基于范围的for循环等新特性。洛谷对 C14、C17 的支持比较友好大部分现代语法都能用。如果你在 OpenJudge 上编译失败最稳妥的办法就是把代码改成纯 C98 风格变量统一在函数开头声明不使用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。