矩阵中的最长递增路径

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

给一个数字矩阵 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 取最大，只认某一格会漏掉最长的那条。