相亲认识一个姐姐，月薪3万多，年终奖6万多，年薪40万左右，刚在东莞买房，总价260万，贷款90多万，每月还贷8k，能追吗?

明明只是个矩阵，结果算法一上来就把我安排得明明白白。

是这样的，这题叫“矩阵中的最长递增路径”，听着像是小学生走迷宫，实际上是大厂面试里专门抓人小辫子的那种题。题目说：给你一个 m x n 的整数矩阵，你要找出最长递增路径的长度——只能上下左右走，不能走对角线，路径上每一步必须比前一步大。

第一次看这题的时候，我是想硬刚 DFS 的。结果一递归，TLE 把我拍得不要不要的。是的，这题要用 DFS，但是必须记忆化搜索，不然你真的在用生命搜索。

咱先不说思路，直接贴个错误示范👇：

publicint longestIncreasingPath(int[][] matrix) {
int m= matrix.length, n = matrix[0].length;
int maxLen=0;
for (int i=0; i < m; i++) {
for (int j=0; j < n; j++) {
            maxLen = Math.max(maxLen, dfs(matrix, i, j, -1));
        }
    }
return maxLen;
}

privateint dfs(int[][] matrix, int i, int j, int prev) {
if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || matrix[i][j] <= prev) {
return0;
    }
int curr= matrix[i][j];
int up= dfs(matrix, i - 1, j, curr);
int down= dfs(matrix, i + 1, j, curr);
int left= dfs(matrix, i, j - 1, curr);
int right= dfs(matrix, i, j + 1, curr);
return 1 + Math.max(Math.max(up, down), Math.max(left, right));
}

这个代码看起来“行云流水”，但是性能惨不忍睹。为啥？因为你会重复计算同一个位置的结果好几次，像极了写需求时不断回到同一个坑里爬不出来的我自己😭。

那正确姿势怎么搞？加缓存啊朋友们！

publicclass Solution {
privatestaticfinalint[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
privateint m, n;

publicint longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return0;
        m = matrix.length;
        n = matrix[0].length;
int[][] memo = new int[m][n];
intmax=0;
for (inti=0; i < m; i++) {
for (intj=0; j < n; j++) {
                max = Math.max(max, dfs(matrix, i, j, memo));
            }
        }
return max;
    }

privateint dfs(int[][] matrix, int i, int j, int[][] memo) {
if (memo[i][j] != 0) return memo[i][j];
intmax=1;
for (int[] dir : dirs) {
intx= i + dir[0], y = j + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                max = Math.max(max, 1 + dfs(matrix, x, y, memo));
            }
        }
        memo[i][j] = max;
return max;
    }
}

看到没，这里用了一个 memo 二维数组来记录每个位置已经算出来的最长路径长度，避免重复计算，相当于给程序上了 turbo。

你以为这就完了？这题还能用 拓扑排序来解。没错，矩阵题竟然能玩出图的套路，有没有点离谱 😅。

说人话就是：每个点是一个节点，存在一个从 A -> B 的边，当且仅当 B > A 并且 B 是 A 的上下左右之一。然后计算图中最长路径，这个在 DAG（有向无环图）里就是经典问题。

但是吧，虽然拓扑也能搞，这题面试中最推荐的还是 DFS + 记忆化。因为写起来直观清晰，面试官也容易 follow，不容易踩雷。

我觉得这题特别有意思的点在于，它其实就是一个“我该不该记住我干过啥”的哲学问题。你如果每次都从头走，那你肯定走不远；只有记住自己走到哪儿最远，别人才好接力走下去（突然有点鸡汤了是不是 😂）。

所以，有时候写代码就跟做人一样，不是靠一味地硬刚，而是得学会聪明地避坑，记住走过的弯路，下次就绕过去了。这题我一开始也踩了不少坑，后来才明白，有时候不是你不会，而是你忘了加缓存罢了。

好啦，说了这么多，其实我现在再看这题，觉得已经挺经典的了，考察的点就那么几个：DFS、记忆化、边界处理、思路转换。但面试嘛，它不就图个你写得出来，讲得明白。大家如果还有哪道算法题被虐得很惨，也欢迎留言一起交流交流，我们一起被虐得优雅点 。