🧗 从递归到 DAG：一次真正理解「最长递增路径」

约 1039 字大约 3 分钟

算法

2026-02-14

有一道很经典的题：

给你一个 n × m 的矩阵，每个格子有高度。

你可以：

从任意格子开始
只能上下左右走
只能走到严格更高的格子

问：最多能走多少步？

第一眼看，这像是个普通 DFS。

但真正写完之后，我意识到——这题根本不是 DFS 的问题，而是图论问题。

一、它到底是什么问题？

如果你把每个格子看成一个点。

当：

grid[a] < grid[b]

并且 b 在 a 的上下左右时。

我们连一条边：

a → b

这意味着什么？

意味着：

所有边都从小指向大
不可能回到原点

它是一张 有向无环图（DAG）

问题瞬间变成：

求 DAG 上的最长路径

一旦看清这一点，题目就简单了。

二、递归到底在做什么？

很多人写递归，但其实并不知道它在算什么。

定义状态：

dp[i][j] = 从 (i,j) 出发，最多还能走多少步

那么状态转移就是：

dp[i][j] = 1 + max(dp[所有比它大的邻居])

这就是完整的数学表达式。

递归不过是把这个式子“翻译成代码”。

三、递归的本质不是向前算，而是向后推

举个简单例子：

1 → 2 → 3 → 4 → 5

调用顺序是：

dfs(1) dfs(2) dfs(3) dfs(4) dfs(5)

但真正计算顺序是：

dfs(5) = 0 dfs(4) = 1 dfs(3) = 2 dfs(2) = 3 dfs(1) = 4

递归的本质是：

走到终点
再从终点往回更新答案

不是往前推，而是往回收。

这就是“自顶向下的 DP”。

四、为什么必须枚举所有起点？

因为这张 DAG 不是连通图。

你只能往更高的地方走。

从某个点出发，不一定能到达所有点。

所以：

答案 = max(dfs(所有格子))

不是只从 (0,0) 开始。

五、真正关键：记忆化

如果没有记忆化，会发生什么？

同一个点会被重复计算。

递归树会指数爆炸。

但一旦加上：

if (dp[x][y]) return dp[x][y];

整棵递归树瞬间压缩成 DAG。

每个点只算一次。

时间复杂度直接降为：

O(n * m)

六、完整代码（标准写法）

#include<bits/stdc++.h>
using namespace std;
int n, m;
int x[4] = { 1,0,0,-1 };
int y[4] = { 0,1,-1,0 };
//传入引用，直接传入为复制时间复杂度较高
int dfs(const vector<vector<int>>& dn, vector<vector<int>>& dp, int h, int l) {
	//如果有则直接返回，防止重复递归
	if (dp[h][l])
		return dp[h][l];
	//获取四个方向中的最大值
	for (int i = 0; i < 4; i++)
	{
		int tn = h + x[i];
		int tm = l + y[i];
		if (tn >= 0 && tn < n && tm >= 0 && tm < m && dn[tn][tm] > dn[h][l]) {
			dp[h][l] = max(dp[h][l], dfs(dn, dp, tn, tm) + 1);
		}
	}
	//返回递归处理后的最大值或者是一个无法下一步的值，此时传回0到上一层
	return dp[h][l];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while (cin >> n >> m) {
		//初始化
		vector<vector<int>> dn(n, vector<int>(m));
		vector<vector<int>> dp(n, vector<int>(m, 0));
		for (int i = 0; i < n; i++)
			for (int k = 0; k < m; k++)
				cin >> dn[i][k];

		int res = 0;
		//必须枚举所有起点。
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				res = max(res, dfs(dn, dp, i, j));
			}
		}
		cout << res << endl;
	}

}