矩阵中的最长递增路径 图解题解

最长递增路径，是在矩阵里找什么

给一个数字矩阵 matrix，从任意一格出发，每步只能上下左右走到值严格更大的相邻格，问最长这样一条路径有几个格。题面 matrix=[[9,9,4],[6,6,8],[2,1,1]]，答案是 4，对应 1→2→6→9 那条，起点终点都不限。

四向随便递归，为什么同一格会被反复走

不做记忆的话，从每一格都发起一次深度优先搜索（DFS，顺一条路探到走不动再回头），四邻里谁更大就往谁递归。问题是同一格被反复重算：值 6 那格往上能走多远，从值 2、值 1 的格各问一遍，都从零往下探。矩阵一大，每格被无数条路重复展开，时间指数膨胀，病根是没把「这格能走出多长」记下来。

每格能走多远，为什么只看更大的邻居

这道题用动态规划解：把每格「能走多远」这个小问题算一次、存好，用到时取。定义 dp[i][j]（i 是行号、j 是列号，都从 0 数起）表示从这格出发能走出的最长递增路径有几个格。每步只能走向更大的格，那下一步只能进四邻里比它大的格，它们还能走多远正是它们的 dp。于是 dp[i][j] = 1 + 四邻里比它大的格的 dp 的最大值，1 是这格自己；四邻都不比它大就是终点，dp 为 1。答案是整张 dp 表的最大值。

严格递增凭什么保证记忆化不会绕死

能把算过的 dp 存下来复用，全靠「严格更大」这三个字。dp[i][j] 只依赖比它值更大的邻居，路径上的值一路严格变大，不会绕一圈回到起点——回去就得踩一个不更大的格，规则不许。没有环，就不会陷入「dp 互相依赖、谁都算不出」的死循环，每格的 dp 靠一批「值更大、已算好」的格就能算出来。于是给每格加个备忘（这就是记忆化：算过一次就存进 memo 表，下次撞到直接取、不再递归），第二次遇到就秒返回。

拿题面这个 3×3 矩阵把 memo 填一遍

按值从大到小填最顺。最大的几格 (0,0)、(0,1) 值 9 和 (1,2) 值 8 四邻都不更大，是终点，memo 记 1。值 6 的 (1,0) 接上更大邻居 (0,0) 的 memo 1，得 2；值 2 的 (2,0) 再接 (1,0) 的 memo 2，得 3。轮到值 1 的 (2,1)，更大邻居里 (2,0) 的 memo 3 最长，接上加自己得 memo[2][1]=4——正是路径 1→2→6→9。其余格同理填好（如 (1,1)、(0,2) 都是 2），九格填完最大 memo 是 4，落在 (2,1)，就是答案。

看着是四向递归，为什么复杂度只有 O(R·C)

记忆化把重复挡在外面。设矩阵 R 行 C 列，每格的 dp 只在第一次访问时真正算一次，之后碰到直接取 memo，计算量就是格子数乘常数，时间 O(R·C)；memo 表加递归栈占 O(R·C) 空间。

严格大小别写松，写成「大于等于」就会在两个相等的格之间来回跳、绕出环，递归停不下来（题面那排 9、那两个 1 都是等值，最易撞上）。空矩阵也得先挡，matrix 一行都没有就返回 0，不然取 len(matrix[0]) 会出错。答案还得扫遍整张 dp 取最大，只认某一格会漏掉最长的那条。

Python

def longestIncreasingPath(matrix):
    R, C = len(matrix), len(matrix[0])
    from functools import lru_cache
    @lru_cache(None)
    def dfs(i, j):
        best = 1
        for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
            ni, nj = i+di, j+dj
            if 0<=ni<R and 0<=nj<C and matrix[ni][nj]>matrix[i][j]:
                best = max(best, 1 + dfs(ni, nj))
        return best
    return max(dfs(i, j) for i in range(R) for j in range(C))

C++

int R, C;
int dfs(vector<vector<int>>& m, vector<vector<int>>& memo, int i, int j){
    if(memo[i][j]) return memo[i][j];
    int best = 1, di[4]={-1,1,0,0}, dj[4]={0,0,-1,1};
    for(int k=0;k<4;k++){
        int ni=i+di[k], nj=j+dj[k];
        if(ni>=0&&ni<R&&nj>=0&&nj<C&&m[ni][nj]>m[i][j])
            best = max(best, 1 + dfs(m, memo, ni, nj));
    }
    return memo[i][j] = best;
}
int longestIncreasingPath(vector<vector<int>>& m){
    R=m.size(); C=m[0].size();
    vector<vector<int>> memo(R, vector<int>(C,0));
    int ans=0;
    for(int i=0;i<R;i++) for(int j=0;j<C;j++) ans=max(ans, dfs(m,memo,i,j));
    return ans;
}

Java

class Solution {
    int R, C;
    int[][] memo;
    int[] di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1};
    public int longestIncreasingPath(int[][] matrix) {
        R = matrix.length; C = matrix[0].length;
        memo = new int[R][C];
        int ans = 0;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                ans = Math.max(ans, dfs(matrix, i, j));
        return ans;
    }
    int dfs(int[][] m, int i, int j) {
        if (memo[i][j] != 0) return memo[i][j];
        int best = 1;
        for (int k = 0; k < 4; k++) {
            int ni = i + di[k], nj = j + dj[k];
            if (ni >= 0 && ni < R && nj >= 0 && nj < C && m[ni][nj] > m[i][j])
                best = Math.max(best, 1 + dfs(m, ni, nj));
        }
        return memo[i][j] = best;
    }
}