矩阵中的最长递增路径

从每个格子暴力 DFS 会重复计算后缀路径。

memo[r][c] 记从该格出发的最长递增路，四方向只走更大值。

① 定义：dfs(r,c)=从该格出发的最长递增路径长度：每个格子算「从我出发，沿严格递增能走多远」，结果存进 memo，重复用到时直接取，不再重算。

② 从最小的 1 出发，只能走向更大的邻居 2：1(在 (2,1)) 的邻居里只有 2(在 (2,0)) 比它大 → 走过去，路径长度 2。

③ 2 → 6：往上走到 (1,0) 的 6：2 → 6（6＞2），路径长度 3，继续找更大的邻居。

④ 6 → 9：到顶，9 无更大邻居 → memo[(0,0)]=1：6 → 9（9＞6），已沿 1→2→6→9 走了 4 步到顶。注意区分：memo 记的是「从该格往后」的最长——9 周围没有更大邻居，从 9 出发只有它自己，所以 memo[(0,0)]=1。

⑤ 回填 memo：9→1、6→2、2→3、1→4 → 最长 4：回溯时层层 +1：memo[(0,0)]=1 → memo[(1,0)]=2 → memo[(2,0)]=3 → memo[(2,1)]=4。对所有格子取最大 → 最长递增路径 ＝ 4。

另一个要点：判环？不用。路径只能严格递增，数值一路变大、绝不回头，所以天然无环，省掉 visited 数组。

边界三连：本题真边界：单格、全等、单行递增。

⑥ 这 4 格 memo 已缓存：别处再经过直接取、不重算：记忆化的威力：这条路径上 4 个格子的最长值都已存好。别的起点(如右下角 1→8)若经过它们，直接读 memo、不再重算 —— 这正是把指数级降到 O(m·n) 的关键。又因严格递增天然无环，全程不需要 visited。

面试追问 · 核心思路：思路：对每格 DFS 求出发最长路径，memo 缓存，取全局最大。

面试追问 · 为何无需 visited：严格递增路径单调，不可能回头，故不用 visited。

面试追问 · 复杂度：复杂度：记忆化每格算一次 O(m·n)。

这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=dp 连刷同类题；卡住时用 AI 答疑问“memo 为什么能让每格只算一次”。