矩阵的最大非负积路径(LeetCode 1594)
哪些公司问过
答案要点
- 负数会让最小值变最大值,需同时维护到达每格的最大积和最小积
- g ≥ 0:mx = max(上mx, 左mx)·g,mn = min(上mn, 左mn)·g;g < 0 时交换来源
- 边界:首行只从左、首列只从上,起点 mx = mn = grid[0][0]
- 取模只在最后做,中间比较大小不能取模,用 64 位整数
- 时间 O(mn),空间可压缩为一维 O(n)
易错点
- 过程中就取模,导致大小比较出错
- 只维护最大值,遇到负数结果错误
- 遇到 0 时处理不当,0 既可能是最大值也可能是最小值
面试官常见追问
- 如果矩阵中有负数,你的 DP 还能用吗?怎么改?
- 中间结果会不会溢出?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场