1. 三个OJ编号同一道滑雪题信息学奥赛一本通 1280是例题OpenJudge NOI 2.6 90是习题洛谷 P1434 是 SHOI2002 原题这三个编号指向的是同一道题在一个二维高度矩阵里从一个格子出发只能滑向上下左右相邻且高度严格降低的格子问最长能滑过多少个格子。这道题在竞赛圈出镜率极高几乎所有学动态规划的人都绕不开它。它表面上是一道“二维网格题”实际考的是有向无环图上的最长路径你可以用记忆化搜索直接写也可以用排序后的递推DP做两种思路对应着两类很常见的解题范式。这篇文章不打算重复题面上已经写清楚的东西而是把题目真正想考察的点、两种解法的完整代码、以及我在多个OJ上反复提交时踩过的坑一次性讲透。适合谁看如果你是刚开始学DP的初学者建议先把样例自己推一遍再对照代码理解“为什么递归函数能当DP用”如果你已经会做但总在某些细节上卡住直接跳到第5节那里列的问题基本都是历年学生错得最集中的地方。1.1 题目到底在问什么给你一个 R 行 C 列的数字矩阵每个数字代表该点海拔。你可以选择任意一个格子作为起点每次只能移动到上下左右相邻的格子并且移动目标格子的高度必须严格小于当前格子的高度。求整条路径最多经过多少个格子。注意两个关键词一是“任意起点”不要求从最高点出发二是“严格小于”高度相等时不能滑过去否则可能出现 5→5 这种既不下降也不上升的无效移动甚至绕圈。经典样例是一个 5×5 的螺旋矩阵最大高度 25 在正中心从 25 出发可以沿着螺旋一路滑到 1路径经过全部 25 个格子所以答案是 25。这个样例很好的说明了“最长路径完全可能经过所有点”也说明答案不等于“最高点的高度”也不等于矩阵大小而是由高度排列结构决定的。1.2 为什么三个平台的题号都值得记很多学生问我同一道题做三遍有什么意义我自己在教学时的看法是这三个平台恰好代表了三种使用场景。信息学奥赛一本通把题放在“例9.24”前面有完整算法讲解适合第一次学的时候跟着例题走。OpenJudge NOI 2.6 的“90:滑雪”挂在动态规划专题下适合按专题刷题输入输出格式和一本通几乎一样提交环境稳定。洛谷 P1434 是原题标签里有记忆化搜索评论区有大量题解适合对完答案后看别人思路或者用不同语言反复提交测试。同一个核心问题在不同OJ上反复出现本身就是一种提醒二维网格上的路径DP是高频考点值得花时间彻底掌握而不是背一道题了事。2. 理解“任意起点”为什么直接DP会翻车我见过不少同学的第一个反应是这题不就是求从最大高度出发能走多远吗先找到最大值再从最大值开始DFS一次就出来了。这个想法看起来合理但完全经不起推敲。假设矩阵是1 2 4 3最大高度是 4从 4 出发只能到 3再到 2再到 1最长路径长度是 4这个例子碰巧对。但如果最大高度周围都是矮子而另一个中等高度的点旁边有一条很长的下降链从最大高度出发反而得不到全局最优解。所以必须“每个点都试一次”也就是把每个格子都当成潜在起点分别求出从它出发能滑出的最长距离最后取最大值。2.1 把滑雪场看成一张有向无环图把每个格子看成一个点如果格子 A 的高度大于相邻格子 B 的高度就画一条从 A 指向 B 的有向边方向是从高到低。因为高度只能严格下降所以沿着边走高度一定越来越小不可能走回头路更不可能形成环。整张图天然是 DAG有向无环图。我们要求的东西翻译成图论语言就是DAG 上从任意点出发到任意点结束的最长路径的边数加一。DAG 上的最长路径问题有一个经典性质只要给定一个合法的拓扑序就能用线性DP求最长路而记忆化搜索本质上是按照递归返回顺序隐式地完成了拓扑序。这里顺便回应一个常见误区有人一看到“最长路径”就想到图论里的 Bellman-Ford 或 Floyd想把所有点对之间的最长路都求出来。且不说 Floyd 在这个矩阵规模下 O((RC)^3) 完全不可行单说本题的图是DAG且边权固定为1根本不需要那么重的工具。用排序DP或者记忆化搜索才是正解。2.2 为什么不能直接按行列顺序递推如果是普通的二维前缀和或者只能向右向下走的路径DP我们可以按行从上到下、从左到右递推因为依赖方向是固定的。但滑雪题四个方向都能走一个格子的答案既可能依赖上方也可能依赖下方。举个例子dp[3][3] 可能被 dp[2][3]上方影响也可能被 dp[4][3]下方影响。如果你强行按行循环算 dp[3][3] 时下方的 dp[4][3] 还没算过直接使用就会出错。这不是代码写错而是递推顺序选错了。那怎么办两个办法第一不要手动控制顺序改用递归记忆化搜索谁需要谁就现算第二利用“高度”这个天然顺序把格子按高度从低到高排序先算矮的再算高的。第3节和第4节分别讲这两种写法。3. 解法一记忆化搜索最不容易写错的写法记忆化搜索是我最推荐初学者使用的解法。它本质是“深度优先搜索 状态缓存”你不需要手动维护拓扑顺序递归返回的天然顺序就是正确的递推顺序。3.1 状态设计与转移定义dp[x][y]表示从(x, y)这个格子出发能滑出的最长路径长度。注意这里“最长路径长度”是按经过的格子数量算的不是按边数。所以边界情况如果某个格子四周要么越界要么高度大于等于当前高度它哪里都去不了那么dp[x][y] 1也就是只包含它自己。转移方程dp[x][y] 1 max(dp[nx][ny])其中(nx, ny)是满足条件的四个相邻格子在矩阵范围内且h[nx][ny] h[x][y]。用递归写就是进入dfs(x, y)时先查缓存如果dp[x][y]已经算过就直接返回否则遍历四个方向递归计算能走的邻居取最大值加一存进dp[x][y]。这样每个格子只会被真正计算一次总体复杂度 O(RC)。3.2 完整C代码#include bits/stdc.h using namespace std; const int N 105; int R, C; int h[N][N]; int dp[N][N]; int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; 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) continue; if (h[nx][ny] h[x][y]) continue; dp[x][y] max(dp[x][y], dfs(nx, ny) 1); } return dp[x][y]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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 \n; return 0; }这段代码在三个OJ上都能直接通过。注意我用dp[x][y] ! 0作为“是否算过”的判断因为合法的路径长度至少是1所以初始全0是安全的。如果你想用memset(dp, -1, sizeof(dp))也可以写法差别不大但判断时记得写if (dp[x][y] ! -1)。3.3 Python递归的特别提醒如果你用 Python 提交直接照抄 C 的递归写法通常会遇到两个问题。第一个是默认递归深度限制。矩阵最大有 10000 个格子最坏情况下递归深度也能到 10000而 Python 默认递归深度只有 1000 左右会直接 RecursionError。所以要在代码开头加一行import sys sys.setrecursionlimit(1000000)第二个是 Python 的函数调用开销比较大。这道题数据量不大加了这个限制后一般能过但如果以后遇到 R、C 更大的版本记忆化搜索可能在 Python 下跑得比较吃力。那时候建议用第4节的排序递推DP。Python 版核心逻辑import sys sys.setrecursionlimit(1000000) R, C map(int, sys.stdin.readline().split()) h [list(map(int, sys.stdin.readline().split())) for _ in range(R)] dp [[0] * C for _ in range(R)] dx [0, 0, 1, -1] dy [1, -1, 0, 0] def dfs(x, y): if dp[x][y]: return dp[x][y] dp[x][y] 1 for k in range(4): nx, ny x dx[k], 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)这里下标从0开始和C的1开始逻辑等价但边界判断千万别写错。4. 解法二按高度排序的递推DP顺便聊复杂度记忆化搜索虽然好写但有些人就是不喜欢递归或者担心递归栈溢出。那么可以换一种思路既然高度严格下降的方向是唯一的合法方向那么“高度”本身就是天然的递推顺序。4.1 从低到高还是从高到低设dp[x][y]仍然表示从当前点出发能滑的最长长度。由于它依赖的是所有比它矮的相邻格子的dp值所以只要保证所有更矮的格子先被算出来当前格子的转移就可以正确进行。最直接的办法是把所有格子按高度从小到大排序然后从矮到高处理。注意一个很容易混淆的点如果你改设dp2[x][y]为“从任意点出发滑到(x, y)的最长长度”那就应该按高度从高到低排序先算高的再算矮的。两种状态都可以做但初学者经常写着写着就把两种定义混在一起结果转移方向全反了。我个人更推荐保持“从当前点出发”的定义因为这样最后答案依然是所有格子dp值的最大值不需要额外考虑终点位置。4.2 排序DP的完整实现#include bits/stdc.h using namespace std; struct Node { int x, y, h; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int R, C; cin R C; vectorvectorint h(R, vectorint(C)); vectorNode v; v.reserve(R * C); for (int i 0; i R; i) { for (int j 0; j C; j) { cin h[i][j]; v.push_back({i, j, h[i][j]}); } } sort(v.begin(), v.end(), [](const Node a, const Node b) { return a.h b.h; }); vectorvectorint dp(R, vectorint(C, 1)); int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; int ans 1; for (const auto p : v) { int x p.x, y p.y; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx R || ny 0 || ny C) continue; if (h[nx][ny] h[x][y]) continue; dp[x][y] max(dp[x][y], dp[nx][ny] 1); } ans max(ans, dp[x][y]); } cout ans \n; return 0; }这个代码的处理顺序是先遍历所有格子把(x, y, h)存进结构体数组然后按h升序排序。当处理到某个格子时所有高度比它小的格子都已经计算完毕那么它四个方向上高度较小的邻居的dp值一定是正确的直接拿来更新即可。高度相同的格子之间不能互相转移因为条件要求严格下降。排序时它们谁先谁后无所谓反正转移时遇到会直接跳过。4.3 两种方法的复杂度对比方法时间复杂度空间复杂度是否依赖递归实现难度记忆化搜索O(RC)O(RC)是低排序递推DPO(RC log(RC))O(RC)否中注意记忆化搜索虽然是递归但每个格子只算一次每条边最多被检查常数次所以整体是 O(RC)。排序递推主要慢在排序不过对本题 R,C ≤ 100 的数据量完全无压力。如果以后遇到类似“二维网格最长递增路径”但 R,C 达到 1000 的题目建议用记忆化搜索或者桶排序优化避免 O(n log n) 的排序成为瓶颈。5. 踩坑实录从一本通提交到洛谷的细节清单这道题代码不长但我在帮学生调错时发现真正出问题的往往不是算法而是一些看着不起眼的细节。下面这些坑每个我都见过不止一次。5.1 数组越界与边界检查C 如果从下标 1 开始读矩阵判断越界的条件要写成nx 1 || nx R || ny 1 || ny C。有些同学从 0 开始读却照抄了 1 开始的判断结果第一行和最后一行永远进不去答案自然变小。这个问题在本地测试小数据时可能不明显因为小矩阵边界少但提交后就会WA。我自己的习惯是C 竞赛题里能用 1 开始就用 1 开始省去很多1/-1的烦恼Python 里就统一从 0 开始用0 nx R这种链式判断不要写nx 0 and nx R的繁琐形式虽然逻辑一样但可读性差一些。5.2 初始化和答案统计的经典误区dp矩阵初始化为 0然后递归里先dp[x][y] 1这是最稳妥的。如果初始化成 -1判断时写成if (dp[x][y] 0) return dp[x][y];也可以。但有些同学把dp初始化成 0递归里却没有先赋 1只在转移时写dp[x][y] max(dp[x][y], dfs(nx, ny) 1);这样孤立格子的dp值永远是 0。最后答案如果直接取max本来应该是 1 的格子会变成 0导致整题答案少 1。在排序递推版本中dp初始化为 1 尤其重要因为最矮的格子没有可转移的邻居它的最长路径就是它自己。漏掉这一步整个递推结果都会偏小。5.3 输入格式和行列顺序一本通、OpenJudge、洛谷的输入格式基本一致先是两个整数 R 和 C然后 R 行 C 列。但有些英文题面会把行和列写作row column先给行后给列这个没问题。真正的坑是部分变种题会先给 C 后给 R或者改名为n m。如果你做完 P1434 后直接套代码去交 POJ 1088 以外的题最好先确认一下行列含义。另外矩阵元素都是整数但题目没有明确说高度互不相同。实际数据里肯定会有相同高度所以转移条件必须是h[nx][ny] h[x][y]而不是。如果误写成虽然同一高度也可以滑但题目要求严格下降这个错误在样例上不一定暴露因为样例里每个高度恰好出现一次但真实数据一测就挂。5.4 递归栈与评测环境C 在 Windows 本地调试时默认栈空间可能不允许递归 10000 层但 Linux 评测机通常没问题。如果你在本地跑大数据直接爆栈可以在代码开头加一句编译选项或者改用排序递推。在洛谷提交时C 递归深度 10000 没压力Python 则必须setrecursionlimit否则会 RE。还有一点正式比赛里如果题目限制栈空间极小记忆化搜索可能会因为爆栈丢分。稳妥做法是掌握两种解法遇到限制再切换。5.5 输出不要多打空格或换行这题只要求输出一个整数。有些同学调试时习惯打印dp矩阵最后忘了注释掉导致多输出了几十行。OpenJudge 对多余输出一般是 WA洛谷可能会提示 Presentation Error但无论哪种都是不必要的失分。提交前把调试输出全删掉只保留cout ans \n;。6. 同题不同包装最长递增路径类问题的通用套路滑雪题之所以经典不只是因为本身常考还因为它是“二维网格最长单调路径”这一类问题的代表。把这个模型吃透很多看起来完全不同的题都能直接套思路。6.1 题目变形一LeetCode 329LeetCode 329 题“矩阵中的最长递增路径”描述是给定一个整数矩阵找出最长递增路径的长度只能上下左右移动且后一个值必须大于当前值。这和滑雪题本质上完全一样只是把“下降”换成了“上升”、把“严格小于”换成了“严格大于”。你只需要把滑雪题的转移条件h[nx][ny] h[x][y]改成h[nx][ny] h[x][y]代码其他地方完全不用动。这也是为什么我强调要理解状态定义而不是背模板状态定义一旦对了方向的微小变化只是条件里的一处符号。6.2 题目变形二不止四个方向有的题会允许 8 个方向即再加上左上、左下、右上、右下四个斜向。这时只需要把方向数组从 4 个元素扩到 8 个int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};其他逻辑完全一致。这类扩展主要考察你是否理解方向数组的作用而不是每次重新发明解法。6.3 通用解题套路总结一下我做这类题的固定流程先判断是否是有向无环图。只要每个点只能走向严格更大/更小的相邻点就不可能形成环DP可用。明确dp[x][y]的状态定义。可以从当前点出发的最长长度也可以是以当前点结束的最长长度选一个自己顺手且转移条件清晰的定义。写记忆化搜索时先查缓存再遍历方向最后返回缓存值。写递推DP时想办法确定一个拓扑序。通常利用数值大小排序或者直接用拓扑排序。最后答案不确定落在哪个点时要全局扫描取最大值不能默认最后一个格子的值就是答案。这个方法不仅适用于滑雪题也适用于很多“网格上最长路径”“自由选择起点终点”的题目。我个人在实际教学里通常要求学生用两种解法各写一遍然后专门把两种写法的初始化、判断条件、答案统计方式放在一起对比。这样做一次比刷三道同类型的新题更有用。这道题最大的价值不是让你记住滑雪的答案而是让你真正理解“递归搜索 状态缓存”和“排序 递推”其实是同一件事的两种表达方式。把这个点想通了后面遇到再复杂的DAG最长路问题你都不会慌。