★ FEATURED ARTICLE 上周有位准备校招的同学找我复盘某头部潮流电商平台的2026春招算法岗笔试题3月21日那场的第三题叫“爬山”。题目本身不是生僻模型但它正好卡在“暴力能想到、但暴力大概率超时”的经典位置上用来筛选候选人有没有真正理解动态规划里的子问题拆分非常典型。我把它完整拆了一遍从题目描述到三种语言实现再到自测边界用例都整理在下面打算参加今年春招的同学可以直接拿来当练习。需要提前说明涉及具体公司信息我统一用“某电商平台”代称。下面是原题回顾和完整解析。1. 题目速览原题描述、输入输出与考察点1.1 原题描述与输入输出格式题目给一个 n 行 m 列的整数矩阵矩阵里每个数字代表该格子的山地高度。你可以从任意一个格子出发每一步移动到上下左右相邻的四个格子之一但目标格子的高度必须严格大于当前格子的高度。同一个格子只能经过一次。问在遵守规则的前提下最多能访问多少个格子。换句话说就是求矩阵中最长的“严格递增”相邻路径长度。输入格式第一行两个整数 n, m 接下来 n 行每行 m 个整数表示每个格子的高度输出格式一个整数表示最长严格递增路径的长度示例输入3 3 9 9 4 6 6 8 2 1 1示例输出4示例里的一条合法最长路径是 1 - 2 - 6 - 9长度 4。注意有两处高度 9 和两处高度 6因为要求严格递增所以相等的格子之间不能互相转移。1.2 为什么“严格递增”这个条件决定了一切如果题目允许相等高度之间移动那路径就可能出现环问题就从最长路径变成带环图上的最长路径难度直线上升通常需要状态压缩之类的手段。加了“严格递增”之后整张图变成一个有向无环图DAG从低处指向高处方向永远不可能绕回低处所以不存在环。在 DAG 上求最长路径有非常成熟的做法既可以记忆化搜索也可以按拓扑序做动态规划。这道题的核心考点就在这里。1.3 数据范围决定了算法上界笔试给出的范围一般是 1 n, m 200也就是最多 40000 个格子。高度值可能到 10^9 级别但这个不影响做法只影响你用 int 还是 long longJava 里用 int 足够了。40000 个点的规模提示我们O(n^2 * m^2) 这种暴力枚举复杂度在极限数据下会到 1.6 * 10^9必挂O(n * m) 或者 O(n * m * log(n * m)) 的算法比较稳妥也就是说明确要求你放弃“每个起点重新搜一遍”的朴素思路去用动态规划的记忆化手段。2. 先想清楚暴力为什么不可行再谈正解2.1 每个点都深搜复杂度是怎么爆掉的最容易想到的解法是枚举每个格子作为起点从起点出发递归四个方向看能走多远。我模拟一下这个过程for 每个格子 (i, j): ans max(ans, dfs(i, j))dfs 里逐层向更高处走。在随机数据下路径一般不会太长这么写可能还能蒙混过关但在故意构造的递增矩阵里路径可以从最小值一路连到最大值几乎覆盖全图。比如一个 200x200 的蛇形递增矩阵最长路径长度能达到 39999。如果从每个格子都重新走一遍每一步又都向四个方向扩散总计算量会接近 O((n*m)^2)也就是 16 亿次级别。笔试直接超时。2.2 重复计算藏在路径交叉的地方假设矩阵里有两条不同的路径都经过同一个高点 X从 A 出发走到 X后续还能走 10 步从 B 出发走到 X后续同样还能走 10 步如果不做缓存这两次搜索会在 X 处把“从 X 出发还能走多远”重复计算一遍。路径交叉越多重复越严重。这其实就是动态规划里最常见的“重复子问题”。一旦你意识到“从某个格子出发的最长路径”是固定的、可复用的值解法就呼之欲出用一个表把结果存起来下次再遇到直接取。2.3 从终点倒推最优子结构定义 dp[i][j] 表示从格子 (i, j) 出发能走的最长路径长度。假设 (i, j) 的四个相邻方向里某个方向 (ni, nj) 的高度大于 height[i][j]那从 (i, j) 出发可以走一步到达 (ni, nj)再继续沿 (ni, nj) 出发的最优路径走所以dp[i][j] max(dp[i][j], 1 dp[ni][nj])如果四个方向都没有更高点那么 dp[i][j] 1表示只能停在这个格子。这个递推式依赖的是“更高的相邻格子的 dp 值”。由于高度严格上升从任意格子出发往高处追最终都会终止在一个“局部最高点”所以递归天然有边界不需要手动处理环。2.4 两条实现路线记忆化搜索 vs 排序动态规划实现上有两条路记忆化搜索用 DFS 递归计算 dp[i][j]每次先查表没算过就算算完存表。排序动态规划把 40000 个格子按高度从小到大排序然后按顺序处理。处理某个格子时它所有更低的邻居都已经算过可以直接用来更新它。两种方法本质一样都是 O(n*m)。区别在于写法。DFS 代码短、思路直观但在极端情况下递归深度可能达到 40000造成栈溢出排序 DP 是迭代写法没有递归深度问题更稳。我下面会给出两个版本的代码。3. 两套正解记忆化 DFS 与排序 DP 的完整推导3.1 方案 A记忆化 DFS代码最短记忆化 DFS 的伪代码如下dfs(x, y): 如果 dp[x][y] 已经算过直接返回 dp[x][y] best 1 依次看四个邻居 如果邻居高度 height[x][y]: best max(best, 1 dfs(邻居)) 保存 dp[x][y] best 返回 best主函数里遍历每个格子调用 dfs取最大值。这套代码最容易写错的地方是忘记判断边界或者忘掉“严格大于”而写成“大于等于”。另外注意初始值用 0 表示“未计算”因为任何格子的 dp 值至少是 1。3.2 方案 B按高度排序的迭代 DP笔试更稳这里我重点展开迭代方案因为它在笔试中最不容易出问题。先准备一个列表把每个格子存成三元组 (height, x, y)。按 height 从小到大排序。再开一个二维数组 longestlongest[x][y] 表示以 (x, y) 结尾的最长严格递增路径长度初始化全部为 1。按高度从小到大遍历每个格子时去看它的四个邻居。如果邻居的高度小于当前格子高度说明这个邻居是“从低处走向当前格子”的前驱而且因为我们是按高度升序处理的这个邻居的 longest 值一定已经算好了。此时可以更新longest[cur] max(longest[cur], longest[neighbor] 1)遍历完所有格子后答案就是整个 longest 数组里的最大值。这里有个细节高度相等的格子不能互相转移所以排序时相同高度的格子之间的先后顺序不影响结果。我们只在邻居高度严格小于当前格子的情况下做更新天然规避了相等高度的问题。3.3 复杂度分析两种方法都够用记忆化 DFS 每个格子只会被真正计算一次每次计算固定看四个方向时间复杂度 O(nm)空间复杂度 O(nm)递归栈空间另算。排序 DP 需要对 40000 个格子排序时间复杂度 O(nmlog(nm))空间复杂度 O(nm)。40000 个点排序非常快在实际笔试里通常和 O(n*m) 的差距可以忽略。如果追求理论最优也可以用拓扑排序 DP 做到严格 O(n*m)但需要额外建图或者处理入度代码复杂度上去了。对笔试场景来说排序 DP 已经足够稳。4. Java、C、Python 三语言实现与避坑注释4.1 Java迭代排序写法import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] height new int[n][m]; Listint[] cells new ArrayList(); for (int i 0; i n; i) { for (int j 0; j m; j) { height[i][j] sc.nextInt(); cells.add(new int[]{height[i][j], i, j}); } } // 按高度从小到大排序 cells.sort((a, b) - a[0] - b[0]); int[][] longest new int[n][m]; for (int i 0; i n; i) { Arrays.fill(longest[i], 1); } int[] dx {1, -1, 0, 0}; int[] dy {0, 0, 1, -1}; int ans 1; for (int[] cell : cells) { int x cell[1]; int y cell[2]; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx n ny 0 ny m height[nx][ny] height[x][y]) { longest[x][y] Math.max(longest[x][y], longest[nx][ny] 1); } } ans Math.max(ans, longest[x][y]); } System.out.println(ans); } }注意cells.sort((a, b) - a[0] - b[0])这里三元组里第一个元素是高度排序不会改变 x、y 的绑定关系没问题。如果高度差值可能超过 int 范围可以改成Integer.compare(a[0], b[0])更安全。4.2 C优先掌握迭代写法#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorvectorint height(n, vectorint(m)); vectorarrayint, 3 cells; // {height, x, y} for (int i 0; i n; i) { for (int j 0; j m; j) { cin height[i][j]; cells.push_back({height[i][j], i, j}); } } sort(cells.begin(), cells.end()); vectorvectorint longest(n, vectorint(m, 1)); int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; int ans 1; for (auto cell : cells) { int x cell[1]; int y cell[2]; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx n ny 0 ny m height[nx][ny] height[x][y]) { longest[x][y] max(longest[x][y], longest[nx][ny] 1); } } ans max(ans, longest[x][y]); } cout ans endl; return 0; }C 里 vector 默认初始化为 0longest我显式用vectorint(m, 1)初始化成 1省得后面手动 fill。4.3 Python递归版要小心迭代版最稳妥先给迭代版import sys def main(): data list(map(int, sys.stdin.read().split())) if not data: return n, m data[0], data[1] idx 2 height [] cells [] for i in range(n): row [] for j in range(m): h data[idx] idx 1 row.append(h) cells.append((h, i, j)) height.append(row) cells.sort(keylambda x: x[0]) longest [[1] * m for _ in range(n)] dx [1, -1, 0, 0] dy [0, 0, 1, -1] ans 1 for h, x, y in cells: for k in range(4): nx, ny x dx[k], y dy[k] if 0 nx n and 0 ny m and height[nx][ny] h: longest[x][y] max(longest[x][y], longest[nx][ny] 1) ans max(ans, longest[x][y]) print(ans) if __name__ __main__: main()Python 的递归版我也贴一下因为很多人面试时想讲记忆化搜索import sys sys.setrecursionlimit(1000000) def solve(): data list(map(int, sys.stdin.read().split())) if not data: return n, m data[0], data[1] idx 2 height [] for i in range(n): height.append(data[idx:idx m]) idx m dp [[0] * m for _ in range(n)] dx [1, -1, 0, 0] dy [0, 0, 1, -1] def dfs(x, y): if dp[x][y] ! 0: return dp[x][y] best 1 for k in range(4): nx, ny x dx[k], y dy[k] if 0 nx n and 0 ny m and height[nx][ny] height[x][y]: best max(best, 1 dfs(nx, ny)) dp[x][y] best return best ans 1 for i in range(n): for j in range(m): ans max(ans, dfs(i, j)) print(ans) if __name__ __main__: solve()这里必须强调递归版虽然思路清晰但在极端递增数据下可能触发 Python 的递归深度上限。就算用sys.setrecursionlimit(1000000)实际运行时也可能因为 C 栈不够而报段错误。所以我个人建议笔试环境优先用迭代排序 DP面试讲解时再提记忆化思路。5. 在线自测指南用样例和边界用例验证代码标题里提到在线测试实际笔试环境一般不会给你太多调试机会自己平时练习时就得把测试用例准备好。我把自己常用的一组用例放在下面建议拿到代码后逐个跑一遍。5.1 先用手算样例验证3 3 9 9 4 6 6 8 2 1 1期望输出 4。这个例子用来确认“严格大于”是否正确以及相同高度值之间不会形成路径。5.2 螺旋递增矩阵最考验实现方式的用例3 3 1 2 3 8 9 4 7 6 5期望输出 9。整个矩阵从 1 到 9 可以绕一圈走完路径长度是 9。这个用例对递归版很不友好因为递归深度正好是 9小矩阵没事但如果改成 200x200 的螺旋递增矩阵递归深度能到 39999也就是我前面说的栈溢出场景。5.3 全相等矩阵和单行矩阵2 2 5 5 5 5期望输出 1因为所有格子高度相同没有可以转移的方向只能停在起点。1 4 4 3 2 1期望输出 4。虽然输入看起来是降序但你可以从最小的 1 出发走 1 - 2 - 3 - 4一共 4 个格子。这道题不要求路径方向只要数字严格递增即可。5.4 自动化对拍用暴力DFS验证两个正解我在本地练习时习惯写一个随机数据生成器再写一个朴素暴力DFS和迭代DP对拍。这里给一个 Python 对拍片段import random def brute(height, n, m): dx [1, -1, 0, 0] dy [0, 0, 1, -1] def dfs(x, y): best 1 for k in range(4): nx, ny x dx[k], y dy[k] if 0 nx n and 0 ny m and height[nx][ny] height[x][y]: best max(best, 1 dfs(nx, ny)) return best ans 1 for i in range(n): for j in range(m): ans max(ans, dfs(i, j)) return ans def sort_dp(height, n, m): cells [(height[i][j], i, j) for i in range(n) for j in range(m)] cells.sort(keylambda x: x[0]) longest [[1] * m for _ in range(n)] dx [1, -1, 0, 0] dy [0, 0, 1, -1] ans 1 for h, x, y in cells: for k in range(4): nx, ny x dx[k], y dy[k] if 0 nx n and 0 ny m and height[nx][ny] h: longest[x][y] max(longest[x][y], longest[nx][ny] 1) ans max(ans, longest[x][y]) return ans for _ in range(1000): n random.randint(1, 5) m random.randint(1, 5) height [[random.randint(0, 9) for _ in range(m)] for _ in range(n)] a brute(height, n, m) b sort_dp(height, n, m) if a ! b: print(mismatch, height, a, b) break else: print(all ok)随机对拍能查出排序方向写反、边界判断漏掉等隐蔽问题。我建议你写完代码后不要只跑示例至少再跑一个全相等矩阵和一个单列矩阵。5.5 这几个各语言易错点务必留意我把练习时踩过的坑汇总成表格易错点表现解决方法边界判断写成nx n漏掉nx 0数组越界或错误答案四方向统一加边界判断相等高度也允许转移输出偏大严格用或Python 没有设置递归上限RecursionError迭代版可完全避免Java 排序比较器直接减法溢出极端值排序错误用Integer.compare忘记初始化 longest 为 1所有答案变成 0初始化时全部填 16. 复盘第三题的位置决定了它的考察重点6.1 这道题在筛什么能力笔试第三题通常不像第四题那样需要复杂的数学建模但一定比前两道“一眼题”更有区分度。“爬山”这道题真正考察三件事能不能从“搜索”快速过渡到“记忆化”能不能识别出“严格递增”带来的 DAG 性质会不会处理大数据范围下的递归深度风险很多人卡在第二点拿到题就写 DFS写完才发现复杂度不对。其实只要在草稿纸上画一个简单矩阵标出从低到高的方向就会意识到这是一个有方向、无环的图。6.2 笔试现场怎么分配时间我的建议是读题加画样例3 到 5 分钟确定模型看到最长路径、无环、40000 点立刻想到 DP 或记忆化5 分钟内写代码迭代排序 DP 大约 15 分钟记忆化 DFS 大约 10 分钟自测至少跑示例和全相等矩阵5 分钟这样总耗时控制在 30 分钟左右留出时间给第四题。如果 15 分钟内没思路先用暴力 DFS 拿部分分再尝试加一个 memo 数组。6.3 如果当场想不起来动态规划怎么写最保险的兜底方案是写一个不带记忆化的 DFS先把小数据分拿满。然后观察自己的 DFS 里哪里重复计算了加一个二维数组缓存返回值即可。大多数情况下“暴力 DFS 缓存表”就是记忆化搜索不需要额外想状态转移。7. 最后想多说两句这道题做完之后我最大的感受是它其实是在提醒我们遇到“路径”“最长”这类词先画图、再定模型而不是急着写循环。我自己第一次做类似的矩阵最长递增路径题时也犯过“每个起点都 DFS”的错误后来被极限数据教训过一次才长记性。如果备考时间充裕建议把这道题和经典的矩阵最长递增路径放一起对比练习把迭代排序 DP 和记忆化 DFS 都写一遍。尤其要亲手构造一个 200x200 的螺旋递增矩阵跑一跑自己的代码看会不会超时、会不会爆栈。经历过一次笔试现场就不会慌了。
阅读完成 · 觉得有帮助？
