做过竞赛刷题的人对这道“滑雪”几乎都不会陌生。信息学奥赛一本通1280、OpenJudge NOI 2.6的90题、洛谷P1434 [SHOI2002] 滑雪三个OJ收录的是同一个题目题面都是“给定一个数字矩阵从任意格子出发每次可以向上下左右滑到高度严格更低的格子求最长滑行距离”。这道题在我眼里属于“必吃透”级别的经典它表面上是个模拟/搜索题实际上讲的是记忆化搜索和动态规划最核心的思想。很多新手拿到题目第一反应是“每个点都DFS一遍”结果小数据能过一到100x100的满数据就超时。这篇文章我就把这题从暴力到优化的完整思路、AC代码、以及我这么多年在这题上踩过的坑一次讲清楚。无论你是刚学完DFS准备接触DP还是已经会写但想搞明白原理都建议完整看一遍。1. 题目到底在说什么先建模再动手1.1 用滑雪场景包装的图论模型先把中文题面翻译成算法语言。给定一个R行C列的矩阵矩阵里每个数字代表该点海拔高度。你可以从任意一个格子开始每一次移动只能走到上下左右相邻的、并且海拔严格低于当前格子的位置问最多经过多少个格子。我第一次做这题的时候第一反应是“这不就是暴力搜索吗从每个点往四个方向走记录最长路径”。这种思路没有错但它忽略了一个关键问题状态数量。R和C最大可以到100矩阵里有10000个点如果每个点都做一次完整深搜路线会指数级增长在极端数据下根本跑不完。正确的切入点是把矩阵看成一个有向图每个格子是一个节点从格子A能滑到格子B就在A和B之间连一条有向边。因为方向必须是从高到低、且高度严格递减所以这个图里不可能出现环。有向无环图DAG上求最长路径这正是动态规划能解决的经典问题。1.2 三个OJ收录的差异与输入输出一本通1280、OpenJudge 90、洛谷P1434题面和数据范围基本一致但提交时有两个小差异要注意。第一是输入顺序。多数版本是先读R行数再读C列数然后按行给出矩阵。有些同学看样例看习惯了以为先读列再读行结果数组下标搞反小数据不一定错但边界数据一定WA。第二是洛谷的评测环境。P1434在这三个OJ里数据量是最大的递归写法如果不做任何优化本地跑得好好的一提交就出现“段错误”或“运行时错误”多半是递归深度太大爆栈了。后面我会专门讲这个问题。1.3 暴力DFS为什么必挂我先说一个反面案例。网上能搜到不少“每个点DFS求最大长度”的代码比如int dfs(int x, int y) { int res 1; for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (合法且更低) { res max(res, dfs(nx, ny) 1); } } return res; }这段代码逻辑没问题问题在于没有记忆化。假设矩阵是随机生成的100x100数字从起点(0,0)出发会分出大量分支更糟的是不同起点到达同一个中间格子的概率非常高这意味着同一个格子会被重复搜索无数次。复杂度最坏可以到O(4^(R*C))哪怕只有30x30的数据都跑不完。有个很直观的测试方法你随便造一个50x50的随机矩阵用暴力DFS跑一下再对比正确解法的耗时差距通常在一百倍以上。这就是“重复计算”带来的代价。2. 记忆化搜索把“重复搜索”变成“读数组”2.1 核心思想DFS加备忘录解决暴力DFS重复计算的方法就是在递归里加一个“备忘录”也就是一个dp数组。我第一次搜索某个格子时把从这个格子出发的最长滑行距离记下来以后再遇到这个格子直接返回记录好的值不再往下递归。这个技巧叫记忆化搜索Memoization。它的本质是“DFS 剪枝”但从算法分类上看它其实就是动态规划的一种实现方式——递归版的动态规划。这里要顺手纠正一个常见的认知误区很多人觉得“记忆化搜索是搜索DP是递推两者没关系”。其实它们是同一件事的两种写法。状态定义一样、转移方程一样区别只在于记忆化搜索用递归从上往下算递推DP用循环从下往上算。滑雪这题用记忆化搜索写代码结构最接近直觉也最好调试。2.2 状态设计与递推公式定义dp[x][y]表示“从格子(x,y)出发能滑行的最长距离”。那么这个格子的答案由它四周能滑过去的格子决定dp[x][y] 1 max( dp[nx][ny] )其中(nx,ny)是(x,y)上下左右、高度严格更小的格子。如果(x,y)周围没有任何一个格子能滑过去也就是它四周要么越界、要么比自己高那么dp[x][y] 1表示这个格子自己就是一条长度为1的路线。这个公式看起来很简单但有一个隐藏前提必须保证计算dp[x][y]时它依赖的那些dp[nx][ny]已经被正确算出。在记忆化搜索里这个前提靠递归天然满足——先递归到底层再一层层返回在递推DP里就要靠“按高度排序”来人工保证这是下一章的内容。2.3 C完整AC代码下面这份代码在三个OJ上都能直接过建议先自己敲一遍再对照看注释。#include bits/stdc.h 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 i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 越界检查 高度严格下降检查 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() { scanf(%d%d, R, C); for (int i 1; i R; i) for (int j 1; j C; j) scanf(%d, 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)); printf(%d\n, ans); return 0; }整个代码的核心其实只有两个地方一个是if (dp[x][y] ! 0) return dp[x][y];另一个是dfs(nx, ny) 1。前者保证每个格子只算一次后者把子问题的答案加上当前这一格构成完整路径长度。2.4 为什么时间复杂度是O(R*C)记忆化搜索的时间复杂度分析是很多同学没搞明白的点。其实非常简单矩阵里一共有RC个格子每个格子最多被完整计算一次第一次调用时会递归展开之后都是直接返回每次计算时最多检查4个方向。所以总时间复杂度是O(RC)空间也是O(R*C)。这个结论要结合“DAG”来理解因为高度严格递减搜索过程不会出现环路递归搜索树实际上是一棵DAG的DFS树。每个节点被访问一次每条边被检查一次复杂度自然就是O(VE)其中VRCE不超过4V。3. 另一种解法按高度排序的递推DP3.1 从低往高推彻底避开递归记忆化搜索写起来很顺手但它本质还是递归依赖系统栈。当矩阵规模变大比如1000x1000递归深度可能达到上万层编译器栈空间不足就会导致程序崩溃。这时候可以考虑递推DP。思路是把矩阵里所有格子按高度从小到大排序然后从最低的格子开始逐个更新它四周比它高的格子。为什么这样能行因为高度严格递减保证了“低处格子的dp值一定先于高处格子被算完”。从最低的格子开始它能往四个方向更新更高的邻居当处理到某个格子时所有比它矮的格子都已经处理完毕所以它的dp值一定是最终值。这其实就是把DAG上的拓扑序用“按高度排序”的方式天然获得了。3.2 排序DP代码与作用过程#include bits/stdc.h 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}; struct Node { int x, y, v; }; int main() { scanf(%d%d, R, C); vectorNode nodes; for (int i 1; i R; i) { for (int j 1; j C; j) { scanf(%d, h[i][j]); nodes.push_back({i, j, h[i][j]}); } } sort(nodes.begin(), nodes.end(), [](const Node a, const Node b) { return a.v b.v; }); int ans 0; for (auto u : nodes) { int x u.x, y u.y; dp[x][y] 1; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; // 注意这里要从低往高更新所以判断条件是 h[nx][ny] h[x][y] 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); ans max(ans, dp[nx][ny]); } } } // 如果矩阵里所有高度都一样上面的更新不会发生ans会一直是0 // 所以最后要遍历一遍取最大值 for (int i 1; i R; i) for (int j 1; j C; j) ans max(ans, dp[i][j]); printf(%d\n, ans); return 0; }这个写法的好处是没有递归没有爆栈风险坏处是需要额外开一个数组存所有节点并排序代码稍微长一点。我第一次写这个版本时犯了一个很经典的错误ans只在更新更高格子的地方取最大值结果遇到“矩阵里所有数字都相同”的数据时全程没有进入更新分支ans一直为0。这种边界数据看起来不起眼却能把不严谨的代码直接打回原形。3.3 记忆化搜索vs排序DP到底选哪个维度记忆化搜索排序DP时间复杂度O(R*C)O(RC log(RC))空间复杂度O(R*C)O(R*C)代码长度短直观较长需要结构体排序栈溢出风险有深数据可能RE无理解难度适合初学者理解DP需要理解拓扑序实际竞赛中R和C不超过100的题两种写法都能过如果R和C到了1000甚至更大我强烈建议用排序DP或者改写成递推别拿递归去赌评测机的栈空间。4. 实战中容易踩的坑这份避坑清单请收好4.1 dp数组初始化为0还是-1很多人第一次写记忆化搜索会问dp数组到底初始化成0还是-1两种都能用但坑不一样。初始化成0判断条件写if (dp[x][y] ! 0) return dp[x][y];这样没问题因为每个格子的答案至少是1不可能为0。但如果你把“至少为1”忘了直接在DFS里写dp[x][y] max(dp[x][y], dfs(nx, ny) 1)初值为0那么对于没有邻居的格子它会被错误地算成0答案直接少1。初始化成-1判断条件写if (dp[x][y] ! -1) return dp[x][y];然后在进入DFS时先dp[x][y] 1;再递归。这种写法更严谨能避免把“未计算”和“答案不存在”混淆。我个人习惯用-1尤其是在写其他更复杂的记忆化题目时。4.2 递归深度导致运行时错误这是洛谷P1434提交中最常见的RE原因之一。100x100的矩阵里如果数据构造得极端高度从左到右、从上到下严格递减那么从左上角递归到右下角深度能到10000层。虽然C在主流OJ上默认栈空间通常能撑住但有些旧OJ或者Windows本地环境会直接崩。我被这个坑坑过一次本地Code::Blocks跑得好好的一提交到洛谷就Runtime Error排查了半天把递归改成递推秒过。后来我写搜索类题目凡是递归深度可能超过5000的都默认用递推版。如果你一定要用递归版可以试试在main函数里加一句扩大栈空间但LOJ不一定支持所以不推荐依赖这招// 不保证所有OJ都支持仅在本地调试时用 #include sys/resource.h // 设置栈空间为 256MBLinux下有效更稳妥的做法直接用第三章的排序DP一劳永逸。4.3 把“严格递减”写成“不增”题目原文说的是“只能滑到高度严格低于当前格子的位置”也就是下一个高度必须小于当前高度。等号的情况不能滑。有些同学为了图省事判断条件写成h[nx][ny] h[x][y]这在大部分随机数据下能跑出看似合理的结果但只要构造一组“相邻高度相等”的数据答案就错了。原因很简单高度相等时路径无法继续不应该被计入路线如果允许相等路线长度会被虚增。这种错误特别隐蔽因为样例数据里往往没有相邻相等的情况本地测怎么都是对的。我后来养成了一个习惯提交前自己构造一组简单数据比如3x3全0矩阵正确答案应该是1再构造从1到9递增的3x3矩阵正确答案应该是9。这两个边界用例一跑多半能暴露问题。4.4 R和C顺序读反别笑这个错误在初学者里出现率极高。题目输入格式是5 5 1 2 3 4 5 ...第一行第一个数是行数R第二个数是列数C。如果你习惯先读C再读R在矩阵是方阵时感觉不到问题一旦变成3行5列的矩形数组下标立刻越界。更隐蔽的是有些OJ的题面会写成“输入第一行为两个正整数M和N表示区域的行数和列数”而有些版本把列数放前面。所以每次做题前先仔细读数据范围那一行别凭经验。下标的边界检查条件也要和R、C保持一致。4.5 答案初始化与多组数据残留这道题只有一个测试用例所以你不需要处理多组输入。但如果你是从其他题目复制过来的模板比如上一题是while (scanf(%d, n) ! EOF)忘记删掉程序就会无限等待第二组数据最后Presentation Error或Time Limit Exceeded。另外ans初始化为0没问题但如果你把ans初始化为-1或者直接对dp[1][1]取初始值就可能在特殊数据下出错。最保险的写法先遍历所有格子逐个用max更新答案确保即使矩阵只有1个格子也能输出1。5. 由滑雪延伸出去记忆化搜索还能干什么5.1 记忆化搜索的本质是“递归状态记录”滑雪这道题教会我们的不仅是“DFS加个数组”这个技巧更是动态规划里最重要的思想用空间换时间把重叠子问题的答案存下来。判断一道题能不能用记忆化搜索有三个条件一是有明显的递归结构可以把大问题拆成小问题二是子问题会重复出现不记录就会重复计算三是状态总数可控存得下。比如斐波那契数列普通递归复杂度O(2^n)加了记忆化变成O(n)这就是最简单的例子。滑雪则是把这一思想应用在二维网格上的典型场景。5.2 一个模型一大堆题学会滑雪后很多题都是它的变体LeetCode 329矩阵中的最长递增路径几乎就是原题只是“滑向更低”变成了“走向更高”一本通和洛谷里的“最长路”模板题比如P1807本质上是DAG最长路径各类棋盘上的路径计数、最短路径问题只要状态有重复都能套记忆化搜索我记得带学生的时候经常说一句话滑雪如果吃透了后面遇到“从任意位置开始、走四连通方向、满足某种单调性、求最长/最短路径”的题思路立马就有了。这类题在省选和NOI题目里反复出现区别只是换了个背景和约束条件。5.3 怎么判断该用暴搜、记忆化还是递推DP经常有人问拿到题到底用哪种写法我的经验是先看数据范围。如果n很小比如n10暴力搜索完全可以如果n到了100甚至1000暴搜基本没戏。这时候再判断有没有重叠子问题——你画一下递归树如果发现同一个子问题会被多次计算就用记忆化搜索或递推DP如果子问题天然不重复那记忆化也帮不上忙。至于记忆化和递推怎么选主要看两点递推顺序难不难找。如果递推顺序不好想比如本题的高度排序或者一些区间DP问题记忆化搜索往往更容易写对。第二个是递归深度会不会超。深度可能很大就老实用递推。滑雪这题两种做法都写一遍会让你对“递归”和“递推”的关系有非常直观的认识。我在带集训队时总是让新手把同一道DP题分别用记忆化和递推写一遍不为别的就为打通这两种思维。最后再分享一个我个人的调试习惯。这类搜索DP题如果交上去WA别急着改算法先把每个格子的dp值打印出来看看。滑雪这题如果某一行全是0多半是初始化或边界问题如果答案只差1大概率是“起始点自身的1”没算进去。打印中间状态是排查这些问题最快的方式比盯着代码干想要高效得多。