1. 项目概述从一道经典算法题看搜索与优化的艺术看到“P1434 [SHOI2002] 滑雪”这个标题很多参加过信息学竞赛或者正在刷题的朋友应该会心一笑。这绝对是一道能让你对“深度优先搜索DFS”、“广度优先搜索BFS”以及“记忆化搜索”产生深刻理解的经典题目。它不像某些偏门的难题那样刁钻而是用一种非常直观的场景——滑雪来考察我们对搜索算法本质的把握以及优化技巧的运用。简单来说题目给你一个二维矩阵代表滑雪场各点的高度你只能从高处向低处滑行要求找出最长的滑行路径长度。这个问题初看似乎简单但如果不加优化地暴力搜索其时间复杂度会是指数级的在数据规模稍大时必然超时。今天我就结合自己多年的刷题和教学经验带大家彻底拆解这道题不仅给出DFS和BFS两种思路的解法更关键的是深入讲解如何通过“记忆化搜索”这一利器将看似不可能的搜索变为高效动态规划并分享一些在实现过程中极易踩坑的细节和调试心得。2. 问题核心与建模将滑雪场景抽象为算法问题在动手写代码之前我们必须把问题理解透彻并建立一个清晰的数学模型。这是解决任何算法问题的第一步也是最关键的一步。2.1 问题重述与输入输出规范题目描述可以这样理解我们有一个 R行 C列的整数矩阵height[R][C]每个单元格的值代表该地点的高度。滑雪者可以从任意一个单元格出发并且每次滑行只能向上、下、左、右四个相邻方向移动。但是移动有一个严格的约束移动到的目标单元格的高度必须严格小于当前单元格的高度。也就是说滑行路径是高度严格递减的。我们需要找到所有可能滑行路径中经过单元格数量最多的那一条路径的长度。这里的“长度”指的是路径上经过的格子数。输入格式通常是第一行两个整数 R 和 C接下来 R 行每行 C 个整数表示高度矩阵。 输出格式是一个整数即最长滑雪路径的长度。例如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开始依次经过24,23,...,1长度为25。2.2 问题本质寻找有向无环图DAG上的最长路径理解了这个规则后我们可以对问题进行抽象图的构建将每个单元格看作图中的一个节点。边的构建如果从单元格 A 可以合法地滑到相邻的单元格 B即height[B] height[A]那么我们就建立一条从节点 A 指向节点 B 的有向边。图的性质由于高度必须严格递减所以在这个图中不可能存在环。从一个高点出发高度不断下降你不可能再回到一个和之前一样高或者更高的点。因此我们构建的图是一个有向无环图Directed Acyclic Graph, DAG。问题转化我们的目标——“寻找最长滑行路径”就等价于在这个 DAG 上寻找最长路径。注意这个最长路径是节点数最多的路径而不是边权之和这里每条边可以视为权值为1。一旦我们将问题建模为 DAG 上的最长路径问题解题的思路就豁然开朗了。对于 DAG 的最长路径一个非常高效且自然的解法就是动态规划DP结合记忆化搜索。注意这里容易产生一个误解认为“搜索”就是 DFS/BFS 遍历。实际上在这道题中DFS/BFS 是实现“状态探索”的手段而“记忆化搜索”是动态规划的一种实现方式核心思想是避免重复计算子问题。3. 解法一深度优先搜索DFS与记忆化搜索这是本题最经典、最直观的解法。我们为每个点(x, y)定义状态dp[x][y]表示从点 (x, y) 出发能滑行的最长路径长度。3.1 状态定义与转移方程为什么这样定义状态因为最终答案ans就是所有dp[i][j]中的最大值。对于每个点(x, y)它的值取决于它能滑向哪些点。基础情况如果点(x, y)四周没有比它低的点那么它自己就是路径的终点dp[x][y] 1路径包含自身。状态转移如果点(x, y)可以滑向点(nx, ny)那么从(x, y)出发的最长路径至少可以走“1 从(nx, ny)出发的最长路径”。我们要在所有可能的下滑方向中选择能带来最长路径的那个。 因此状态转移方程可以写作dp[x][y] max(dp[x][y], 1 dp[nx][ny])其中(nx, ny)是(x, y)所有合法的高度更低的邻居。这个方程是递归定义的要知道dp[x][y]需要先知道它所有邻居的dp值。这正是递归计算的典型场景。3.2 递归DFS函数的设计与实现我们设计一个递归函数dfs(x, y)它的返回值就是dp[x][y]。// 假设全局变量R, C, height[R][C], dp[R][C]初始化为0 // 方向数组dx[4] {-1, 1, 0, 0}, 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 0 nx R ny 0 ny C height[nx][ny] height[x][y]) { // 关键递归计算从邻居出发的最长路径然后更新当前点 dp[x][y] max(dp[x][y], dfs(nx, ny) 1); } } // 返回从(x,y)出发的最长路径长度 return dp[x][y]; }3.3 记忆化搜索避免重复计算的关键上面的代码中if (dp[x][y] ! 0) return dp[x][y];这一行就是记忆化搜索的灵魂。dp数组在这里扮演了两个角色存储计算结果dp[x][y]最终存储了dfs(x,y)的返回值。标记是否已计算初始化时我们将其设为0或-1等特殊值。当某个点的dp值不为初始值时说明它已经被计算过了我们可以直接返回这个值而无需再次进行递归展开。为什么这能避免重复计算考虑一个简单的例子点A可以滑向点B和点C而点B和点C都可以滑向点D。在计算dfs(A)时我们会调用dfs(B)和dfs(C)。而dfs(B)和dfs(C)又都会去调用dfs(D)。如果没有记忆化dfs(D)会被计算两次。当图规模变大、结构更复杂时这种重复计算是指数级增长的会导致严重的性能问题。记忆化搜索确保了每个状态每个(x,y)点只被计算一次时间复杂度优化到了 O(R*C)因为每个点最多被访问一次每次访问检查四个方向是常数时间。实操心得dp数组的初始化值选择有讲究。这里我们用0因为路径长度至少为1所以0可以安全地表示“未计算”。但在某些问题中结果可能为0这时就需要用-1等特殊值来初始化并在判断时区分“未计算”和“计算结果为0”。3.4 主函数逻辑与复杂度分析在主函数中我们需要遍历每一个点(i, j)计算dfs(i, j)并维护一个全局最大值ans。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 endl;时间复杂度由于记忆化的存在每个节点(i, j)的dfs函数至多被执行一次主体逻辑递归部分每次执行需要检查4个方向。因此总时间复杂度为O(4 * R * C) O(R * C)是线性的效率非常高。空间复杂度主要是dp数组和递归栈的开销。dp数组是 O(R * C)。递归栈的深度在最坏情况下等于最长路径的长度即 O(R * C)但实际由于高度递减通常不会这么深。空间复杂度为O(R * C)。4. 解法二广度优先搜索BFS与拓扑排序思路虽然DFS记忆化是更自然的解法但我们也完全可以利用BFS的思想来解决。不过这里的BFS不是直接用于求最长路径而是用于确定一个合理的计算顺序。4.1 思路转换从出度到入度在DFS解法中我们定义dp[x][y]为从该点出发的最长路径。状态转移依赖于后继节点出边。 我们可以换一种定义方式定义f[x][y]为以该点结束的最长路径长度。那么状态转移就依赖于前驱节点入边f[x][y] max(f[px][py]) 1其中(px, py)是所有能滑到(x, y)的点即height[px][py] height[x][y]。最终答案同样是所有f[i][j]的最大值。4.2 基于BFS拓扑排序的动态规划这种定义下计算f[x][y]需要所有比它高的邻居前驱都已经计算完毕。这引导我们想到拓扑排序。在DAG中我们可以按照一种线性顺序拓扑序来遍历节点使得对于任意一条边 (u-v)u 都在 v 之前被访问。这样当我们计算 v 时它的所有前驱 u 必然已经计算完成。如何获得这个拓扑序一个标准方法就是使用队列BFS进行拓扑排序计算每个点的入度。在这里入度就是能滑向该点的邻居数量即高度比它高的邻居数。将所有入度为 0 的点即“最高点”没有更高的点能滑向它加入队列并初始化它们的f值为 1路径只有自己。进行BFS弹出队首节点(x, y)遍历它所有出边即它能滑向的、更低的邻居(nx, ny)。因为(x, y)已处理相当于从图中“移除”该点及其出边所以邻居(nx, ny)的入度减1。同时用f[x][y] 1去更新f[nx][ny]因为找到了一个更长的、以(nx, ny)结束的路径。如果邻居(nx, ny)的入度减为0说明所有能滑向它的点都已处理完毕它的f值已经确定将其加入队列。队列为空时拓扑排序完成所有f值均已计算完毕。4.3 代码实现细节#include iostream #include queue #include vector #include algorithm using namespace std; struct Point { int x, y; }; int main() { int R, C; cin R C; vectorvectorint height(R, vectorint(C)); vectorvectorint f(R, vectorint(C, 1)); // 初始化为1 vectorvectorint inDegree(R, vectorint(C, 0)); int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; // 读入数据并计算初始入度 for (int i 0; i R; i) { for (int j 0; j C; j) { cin height[i][j]; } } for (int i 0; i R; i) { for (int j 0; j C; j) { for (int d 0; d 4; d) { int ni i dx[d]; int nj j dy[d]; if (ni 0 ni R nj 0 nj C) { if (height[ni][nj] height[i][j]) { // i,j 能滑向 ni,nj说明 (ni,nj) 有一条入边来自 (i,j) // 所以 (ni,nj) 的入度加1 inDegree[ni][nj]; } } } } } queuePoint q; // 将所有入度为0的点局部最高点入队 for (int i 0; i R; i) { for (int j 0; j C; j) { if (inDegree[i][j] 0) { q.push({i, j}); } } } int ans 1; // 至少为1 while (!q.empty()) { Point cur q.front(); q.pop(); int x cur.x, y cur.y; ans max(ans, f[x][y]); // 更新答案 // 遍历当前点的出边滑向更低的点 for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 nx R ny 0 ny C height[nx][ny] height[x][y]) { // 状态转移尝试用当前路径更新邻居 f[nx][ny] max(f[nx][ny], f[x][y] 1); // “移除”当前点邻居入度减1 inDegree[nx][ny]--; // 如果邻居入度变为0说明所有能到达它的更高点都已处理其f值已确定入队 if (inDegree[nx][ny] 0) { q.push({nx, ny}); } } } } cout ans endl; return 0; }4.4 两种解法的对比与选择特性DFS 记忆化搜索BFS 拓扑排序 DP状态定义dp[x][y]: 从(x,y)出发的最长路径f[x][y]: 以(x,y)结束的最长路径核心思想递归计算记忆化避免重复子问题拓扑排序确定计算顺序递推更新实现难度相对简单直观递归代码简洁稍复杂需要维护入度队列计算顺序隐式地由递归调用决定自顶向下显式地由拓扑序决定自底向上从高到低适用场景绝大多数DAG最长/最短路径问题需要显式拓扑序或处理层级关系时个人建议首选更符合直觉代码易写易调试作为理解拓扑排序和另一种DP思路的练习对于本题DFS记忆化搜索是更优的选择因为它代码更短思维更直接。BFS解法虽然同样高效时间复杂度也是 O(R*C)但实现起来稍显繁琐。不过理解BFS解法有助于你掌握拓扑排序这一重要工具在处理更复杂的依赖关系问题时非常有用。5. 常见问题与调试技巧实录即便理解了算法在实现时依然会遇到各种问题。下面是我在多次实现和教学中总结的一些常见坑点和解决技巧。5.1 递归深度与栈溢出问题虽然用了记忆化但递归调用深度在最坏情况下可能等于路径长度对于 R、C 达到 100 量级的矩阵最长路径可能接近 10000这会导致递归深度过深在某些编程环境或竞赛平台上可能引发栈溢出Stack Overflow。解决方案编译器优化在C中可以尝试使用编译指令#pragma GCC optimize(O2)以及-O2优化选项有时能缓解栈压力。迭代加深搜索IDS不适用。本题不是搜索可行解而是计算最优值。转换为显式栈的迭代DP这是最根本的解决方法。我们可以按照高度对所有点进行排序然后从低到高或从高到低进行递推。因为滑行方向是高度递减所以从低点向高点递推以该点结束需要找更高的邻居从高点向低点递推从该点出发需要找更低的邻居。排序后可以确保计算每个点时它所依赖的邻居都已经被计算过。// 思路按高度升序排序从低到高计算以该点结束的最长路径 struct Node { int h, x, y; }; vectorNode nodes; for (int i0; iR; i) for (int j0; jC; j) nodes.push_back({height[i][j], i, j}); sort(nodes.begin(), nodes.end(), [](const Node a, const Node b){ return a.h b.h; }); vectorvectorint f(R, vectorint(C, 1)); for (auto node : nodes) { int xnode.x, ynode.y; for(int d0; d4; d){ int nxxdx[d], nyydy[d]; if(nx0 nxR ny0 nyC height[nx][ny] height[x][y]){ // 因为nodes按高度升序height[nx][ny] height[x][y]意味着(nx,ny)在node之前被处理 // 注意这里逻辑错了。按升序处理当处理到(x,y)时比它低的点(nx,ny)已经在前面处理过了。 // 但我们要找的是更高的前驱来更新当前点。所以应该检查更高的邻居。 // 正确写法if(height[nx][ny] height[x][y]) { f[x][y] max(f[x][y], f[nx][ny]1);} } } } // 或者按降序排序计算从该点出发的最长路径会更直观。踩坑记录我最初尝试排序法时就在这个邻居判断的逻辑上绕晕了。关键在于明确你的状态定义和计算顺序。如果按高度升序排计算f[x][y]以该点结束就应该去查找更高的邻居前驱但更高的邻居可能还没被处理因为它在数组后面。所以按高度降序排序并计算dp[x][y]从该点出发去查找更低的邻居后继这样更低的邻居一定已经先被处理了因为高度更低在降序数组中排在后面不对降序是高的在前低的在后。处理到高点时低点还在后面没被处理。看来排序法需要仔细设计。一个稳妥的排序DP是将点按高度升序排序然后遍历对于每个点用它去更新比它低的邻居。这样保证了更新时源点高的点的dp值已经确定。5.2 记忆化数组的初始化陷阱问题dp数组初始化为0但路径长度可能为1。如果某个点的最长路径确实就是1四周没有更低点dfs会计算它并赋值为1。这没问题。但是如果矩阵中本身有高度为0的点呢这也不影响因为我们的判断条件是dp[x][y] ! 0计算过的点会被赋值为正数1。所以用0表示“未访问”是安全的。更通用的做法为了绝对清晰可以初始化为-1。vectorvectorint dp(R, vectorint(C, -1)); int dfs(int x, int y) { if (dp[x][y] ! -1) return dp[x][y]; // 判断是否已计算 dp[x][y] 1; // 初始化 // ... 递归逻辑 return dp[x][y]; }5.3 方向数组的运用与越界检查这是一个基础但容易出错的地方。一定要在访问height[nx][ny]之前先检查nx和ny是否在[0, R)和[0, C)的范围内。否则会导致数组越界程序运行时可能崩溃或产生不可预知的结果。// 正确的检查顺序 if (nx 0 nx R ny 0 ny C) { if (height[nx][ny] height[x][y]) { // 再检查高度条件 // ... } }5.4 多组数据输入的清空在在线判题系统OJ中题目可能包含多组测试数据。如果你使用全局变量或静态数组在处理完一组数据后必须将dp数组、height数组等重新初始化否则上一组数据的结果会干扰下一组。while (cin R C) { // 假设输入直到EOF // 重新初始化或清空vector vectorvectorint height(R, vectorint(C)); vectorvectorint dp(R, vectorint(C, 0)); // 每次循环新建自然清空 // ... 计算逻辑 }5.5 性能优化小技巧对于极限数据如 R,C100O(R*C) 的算法完全足够。但如果你还想追求极致的速度使用原生数组代替vector在确定最大规模后使用int dp[105][105]静态数组访问速度通常比vectorvectorint稍快且可以减少动态内存分配的开销。使用快速输入输出在C中对于大量数据输入使用cin和cout可能较慢。可以关闭同步流或使用scanf/printf。ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // 然后使用 cin, cout递归函数内联对于简单的递归函数编译器可能会自动内联。也可以尝试使用inline关键字但效果取决于编译器。6. 从本题延伸的算法思维训练“滑雪”这道题之所以经典是因为它完美地串联了搜索、动态规划和图论的基本思想。掌握它不仅能解决这一道题更能获得解决一类问题的能力。6.1 记忆化搜索是动态规划的“另一副面孔”很多同学觉得动态规划DP的状态转移方程难想递推顺序难确定。记忆化搜索提供了一种“逆向”思考的方式从终点往回看。在这道题中“从 (x,y) 出发的最长路径”这个状态定义用递归来实现非常自然。你只需要思考如果我现在站在 (x,y)我下一步能去哪然后交给递归去解决子问题。记忆化则保证了子问题不被重复解决。这其实就是“自顶向下”的DP它常常比“自底向上”的递推更容易构思。6.2 如何识别此类问题当你遇到一个问题具有以下特征时可以优先考虑DFS/BFS记忆化或DP求最优解最长、最短、最大、最小。问题可以分解为子问题并且子问题有重叠即不同的决策路径可能会到达相同的状态。状态空间可以表示通常是二维、三维坐标或者某种状态编码。存在明确的转移方向如本题的高度递减构成了DAG。类似的问题有数字三角形、棋盘上的行走方案数某些限制下、最长上升子序列LIS的二维泛化等。6.3 调试与验证从小规模数据开始当你写出代码后不要急于提交到OJ。应该自己构造一些小规模的数据进行测试。测试用例11x1的矩阵答案应为1。测试用例2所有高度相同答案应为1因为无处可滑。测试用例3严格递增的一行如1 2 3 4 5答案应为5从5滑到1。测试用例4严格递减的一行答案应为1从任意点出发都无法滑向邻居。测试用例5一个简单的2x2矩阵手动计算验证。使用cout打印出dp数组的中间结果与你的手动推导进行对比是发现逻辑错误最有效的方法。最后这道题最好的学习方法就是自己动手实现一遍。先尝试写出不加记忆化的DFS感受一下它为什么慢可以尝试 RC10 且高度随机可能就会超时。然后加上记忆化体会性能的飞跃。再挑战一下BFS拓扑排序的写法巩固对图论算法的理解。这个过程本身就是一次扎实的算法训练。