矩阵中的最长递增路径(LC329)
哪些公司问过
答案要点
- memo[i][j] 表示从该格出发的最长递增路径长度
- 只向值严格更大的相邻格转移,取最大值加一
- 严格递增保证无环,不需要 visited 数组
- 每格计算一次,时间与空间 O(mn)
- 可改用拓扑排序按层 BFS,避免递归过深
易错点
- 不加记忆化,直接 DFS 导致指数级时间
- 误以为需要 visited 数组并在回溯时清除,影响记忆化
- 只从某一个起点出发,没有遍历所有格子
面试官常见追问
- 如果改成非严格递增(可以相等)还行吗?
- 拓扑排序版本怎么写?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场