看到 LeetCode 1594“矩阵的最大非负积”这个题我第一反应是又是经典的网格 DP从左上角走到右下角每次只能往右或往下套路我都懂。真正动手写的时候才发现“最大非负积”这六个字把难度从入门拉到了中等偏上。题面很简单但涉及到负数相乘、最大值和最小值的对称维护、大数取模几个点一起落下来代码一旦写急就很容易翻车。这道题在面试和刷题里很有代表性它表面是网格 DP实际在考“状态是否覆盖了所有可能影响决策的信息”。你不光要看走到的位置还要看这个位置上的乘积是正是负、是大是小。正的最大值乘上负数会变成负的最小值负的最小值乘上负数反而能变成正的最大值。如果一开始没想清楚这一层后面所有代码都是错的。这篇我用一点点偏实战的视角把这道题的思路、代码、坑以及几个延伸想法一次性说清楚。1. 题目拆解核心考点到底藏在哪1.1 题目在问什么给你一个二维矩阵从左上角出发每一步只能向右或向下走直到右下角。整条路径上所有格子里的整数要乘起来得到一个总乘积。目标是让这个总乘积最大但有一个额外限制结果必须是非负数。如果无论如何走所有路径的乘积都是负数就返回 -1。输入约束我记得比较清楚矩阵的行和列都在 15 以内每个格子的值在 -100 到 100 之间。别看矩阵不大路径长度也就二十几个格子但连乘起来的数值会非常大所以题目还有一个细节最后要按题意对结果取 10^9 7 的模。这里有个很容易被忽略的点返回的不是“模意义下最大”的那个值而是“真实乘积最大且非负”的那个值再取模。这个区别后文会专门讲。从模型上看“只能向右和向下走”决定了这是一个有向无环图天然适合动态规划。但如果只是简单地用 dp[i][j] 记录到达某个格子的最大乘积那就会踩进负数这个坑里。1.2 为什么很多解法一开始就走偏很多人包括我一开始的思路是定义 dp[i][j] 表示从起点到当前格子的最大乘积。转移方程也很简单把上面和左边两个来源中较大的一个拿过来乘上当前格子的值取一个最大值就完事了。这个思路在最普通的“最大路径和”里完全正确但放到乘法场景里会出问题。我举个例子假如当前格子的值是 -2上面来源的最大乘积是 10左边来源的最大乘积是 -5。如果只看最大值 1010 乘上 -2 得到 -20看起来很糟糕。可是左边那个 -5 乘上 -2 得到 10反而是能延续下去的数值。更关键的是如果后面再遇到一个负数这个 10 再乘一次负数又会变负反而是原来那个 -20 再乘负数能变成正的 40。所以说在乘法 DP 里最大乘积并不是唯一需要关心的状态。很多时候一个看起来“很差”的最小值恰恰是未来翻盘的关键。这就是这道题最核心的考点状态设计必须同时保留最大值和最小值。1.3 这道题对应的底层能力把一个简单的单值 DP 升级成双值 DP不是一个凭空出现的技巧它背后是一种状态建模能力你要分析的是“下一步的决策到底依赖当前哪些信息”。在加法场景里大就是好所以只需要保留一个最大值。在乘法场景里符号会反转大和小都有价值所以两个极端都要留。这种能力在真实开发里也有映射。比如在一个链路系统里某个指标的最大值并不代表后续收益最大因为中间可能有各种“反向调节”因素。你建模的时候少留了一个维度后面所有优化都是空中楼阁。LeetCode 题目虽小但它训练的是这个直觉。2. 双状态动态规划的原理与状态设计2.1 为什么 dpMax 和 dpMin 要一起维护设 dpMax[i][j] 为到达格子 (i,j) 时所有可能路径乘积中的最大值dpMin[i][j] 为所有可能路径乘积中的最小值。为什么要最小值因为当前格子的值如果是负数那么“最小值”乘上它可能变成“最大值”。如果当前格子的值是正数那么“最大值”乘上它仍然是“最大值”“最小值”乘上它也仍然是“最小值”。所以不管当前值是正还是负只要同时拿出上一步的最大值和最小值乘一下再统一比较就不会遗漏任何翻身机会。这个逻辑跟一维数组里的“乘积最大子数组”那题是同一个灵魂。区别只在于那道题是一维的本题是二维的。一维场景里你维护 preMax 和 preMin二维场景里你把这两个值铺到网格每个格子上。2.2 转移方程怎么写对于格子 (i,j)设 val grid[i][j]。它只能从上方 (i-1,j) 或左方 (i,j-1) 过来。对于每一种来源它都有两个候选来源的最大值乘上 val以及来源的最小值乘上 val。我习惯先把候选全收集起来再统一取最大最小。也就是来源是上方时候选值有dpMax[i-1][j] * val、dpMin[i-1][j] * val。来源是左方时候选值有dpMax[i][j-1] * val、dpMin[i][j-1] * val。dpMax[i][j] 取所有候选值中的最大值。dpMin[i][j] 取所有候选值中的最小值。写成公式就是这样dpMax[i][j] max( dpMax[i-1][j] * val, dpMin[i-1][j] * val, dpMax[i][j-1] * val, dpMin[i][j-1] * val ) dpMin[i][j] min( dpMax[i-1][j] * val, dpMin[i-1][j] * val, dpMax[i][j-1] * val, dpMin[i][j-1] * val )有边界时只需要把不存在的来源去掉。比如第一行的格子没有上方来源就只看左边第一列的格子没有左边来源就只看上方。2.3 初始化比转移更容易被忽略起点 (0,0) 的初始化没有争议dpMax[0][0] dpMin[0][0] grid[0][0]。真正的坑在第一行和第一列。有一种常见做法是先把第一行、第一列单独初始化dpMax[0][j] dpMin[0][j] dpMax[0][j-1] * grid[0][j] dpMax[i][0] dpMin[i][0] dpMax[i-1][0] * grid[i][0]第一行和第一列都只有一条路径所以最大值和最小值是同一个值不需要分两支维护。这个单独初始化是安全的也方便理解。如果不想单独初始化也可以在双重循环里用 if 判断来源是否存在。两种情况都行但千万不要给 dpMax 和 dpMin 的初始值设为 0。很多第一次写的人是这样想的反正后面会更新0 就 0 吧。结果第一行如果遇到负数别人把你第一行的最大值和最小值都初始成了 00 乘上任何数都是 0负数路径的真实乘积被直接抹掉了。后续就算遇到负负得正这些路径也永远丢失。我推荐用“来源是否存在”的写法代码更统一也天然规避了第一行第一列的初始化问题。对于来源不存在的格子直接跳过对应候选即可。因为题目给的矩阵中我会先把 dpMax 和 dpMin 都建出来从 (0,0) 开始遍历用 None 或哨兵表示不可用的来源。2.4 为什么这个状态设计不会漏解要证明双状态 DP 不漏解可以用一个直觉式的归纳证明假设到达 (i,j) 的所有路径中最大值为 max最小值为 min。那么对于任意一条路径它的乘积都在 max 和 min 之间。下一步无论当前格子的值是正数还是负数所有可能的新乘积都会落在 {max * val, min * val} 这两个极端值所能覆盖的范围两侧。更直接地说正数乘以区间内任何数最大值一定由原最大值产生最小值一定由原最小值产生负数乘以区间内任何数最大值一定由原最小值产生最小值一定由原最大值产生。所以你看两个来源各贡献两个候选值再取 max/min得到的仍然是新的最大值和最小值。这个归纳成立算法也就成立。3. 代码实现与逐行解读3.1 一个能直接跑通的 Python 版本我用 Python 写一个最清晰、最不容易出错的版本。注意 Python 的整数可以自动扩展不需要额外处理大数溢出这也是为什么很多人在刷这道题时喜欢用 Python。from typing import List MOD 10 ** 9 7 class Solution: def maxProductPath(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) dp_max [[0] * n for _ in range(m)] dp_min [[0] * n for _ in range(m)] dp_max[0][0] grid[0][0] dp_min[0][0] grid[0][0] for i in range(m): for j in range(n): if i 0 and j 0: continue candidates [] if i 0: candidates.append(dp_max[i - 1][j] * grid[i][j]) candidates.append(dp_min[i - 1][j] * grid[i][j]) if j 0: candidates.append(dp_max[i][j - 1] * grid[i][j]) candidates.append(dp_min[i][j - 1] * grid[i][j]) dp_max[i][j] max(candidates) dp_min[i][j] min(candidates) if dp_max[m - 1][n - 1] 0: return -1 return dp_max[m - 1][n - 1] % MOD这个版本的重点是不是把所有候选值简单一拼就完事而是先收集再统一求 max 和 min。这样代码读起来很清楚也不会因为方向判断繁复杂乱而写错。3.2 用例题手推一遍 DP 表拿官方示例里的矩阵来验算grid 是1 -2 1 1 -2 1 3 -4 1我们一层层填表。起点 dpMax[0][0] 1dpMin[0][0] 1。第一行因为没有上方来源只能从左往右1 乘 -2 得到 -2再乘 1 得到 -2所以第一行的 dpMax 和 dpMin 都是 -2。第二行第一列只能从上往下1 乘 1 得到 1所以 dpMax[1][0] dpMin[1][0] 1。第二行第二列的值是 -2上方来源 dpMax[0][1] -2、dpMin[0][1] -2候选值为 4 和 4左方来源 dpMax[1][0] 1、dpMin[1][0] 1候选值为 -2 和 -2。最终 dpMax[1][1] 4dpMin[1][1] -2。继续算最后右下角的 dpMax 会得到 8dpMin 会得到一个负数。8 就是所有路径里的最大非负乘积。这个例子也说明了如果你只保留最大值第二行第二列的时候你拿的是 1乘上 -2 得到 -2后面就会一路错下去只有同时保留最小值 -2 和 4才能在下一轮遇到负数时把局势扳回来。3.3 关于取模和数值溢出这里要单独聊题目里有个很容易被误解的点求的是“真实最大非负乘积”的模不是“模意义下最大的乘积”。这两个概念不一样。加法场景里如果每一步都对 10^9 7 取模不会影响大小比较因为加法模运算保持大小关系。但乘法场景里不是这样。举个抽象例子假设真实值 A 大于真实值 B但 A 取模后反而小于 B 取模后。如果你在中间状态就取模dpMax 存的就不再是真实最大值后续所有转移都会失真。所以正确做法是在 DP 全过程中保留完整的大整数只在最后返回时取模。Python 的 int 天然支持任意精度直接这么写就行。用 C 或 Java 的话如果乘积可能超过 long但要符合 10^97 的取模要求就得用 BigInteger 或者自定义符号加对数压缩存储。很多网上题解直接用 long long是因为部分测试数据没有把 64 位顶爆但从原理上说严谨的做法还是要用大数或定制的双状态来保留大小关系。这道题我觉得根本没必要为了省那点空间去做 1D 空间压缩因为 m 和 n 最多 15两个二维数组也就多开几百个格子。代码可读性更重要。如果你真想压可以压成两个长度为 n 的一维数组从左到右更新dp[j] 保存当前行的值dp[j-1] 保存上一行在当前列之前的状态。面试里可以提一嘴但不要在这里秀操作容易踩坑。4. 常见错误与排查思路4.1 只维护单值 DP 导致漏掉负负得正这是最容易踩的坑。症状是小样例能过遇到带负数的矩阵就错。排查方法很简单手动构造两个反例测一下第一个例子1 -2 -2 1如果只维护最大值左上角 1右上角 1 乘 -2 -2左下角 1 乘 -2 -2右下角取 max(上方 -2 乘 1, 左边 -2 乘 1) -2最后返回 -1。但实际上有一条路径是 -2 乘 -2 4答案应该是 4。只要维护了 dpMin右下角的 dpMin 是 1乘上右下角的值 1 仍然是 1dpMax 是 -2 乘 -2 4马上就对了。这类错误属于“状态建模不全”不是边界写错所以要回看状态定义和转移方程。4.2 第一行第一列初始化为 0有些解法用 0 填充两个 DP 数组结果第一行或第一列有负数时全部乘积被 0 覆盖。比如 grid[0][1] -5如果 dpMax[0][0] 是 1dpMax[0][1] 应该等于 1 乘 -5 -5但因为数组初始值是 0且转移时取了 max(0, 0 乘 -5)最后会得到 0直接把真实路径弄丢了。解决方式是用我前面给的“来源是否存在”的判断而不是依赖哨兵值。判断条件 i 0 和 j 0 是显式且可靠的永远不会被数值污染。4.3 把“最大非负积”当成“最大正数”非负包含 0。如果所有路径的乘积都是负数返回 -1。但如果有一条路径的乘积是 0哪怕其他所有路径乘积都小于 0答案也是 0应该返回 0而不是 -1。我记得官方例子里就有个矩阵1 3 0 -1两个路径分别为 1 乘 3 乘 -1 -3以及 1 乘 0 乘 -1 0。正确答案是 0。如果你在最后判断if dp_max 0返回 -1这句话是没问题的但如果你判断成if dp_max 0返回 -1那就错了因为 0 是非负积题目要求的是“最大非负积”0 完全合法。4.4 中间结果直接取模一旦你开始对 dpMax 和 dpMin 取模错误会在很远的地方显现出来。因为取模后的数值大小不仅不代表真实大小符号信息也可能丢失。比如 dpMin 存了一个负数取模后变成正数下一步再乘一个负数时完全不知道原值是正是负。有些解法为了处理大数用 Python 但仍在每一步取模我建议不要这样做。Python 大整数在这个规模下完全没压力真没必要引入取模带来的正确性风险。取模只应该出现在最终返回那一行。4.5 遍历顺序写反网格 DP 要求从左上到右下逐行更新因为 (i,j) 依赖 (i-1,j) 和 (i,j-1)。如果你用列优先遍历也就是先 j 再 i某些格子的来源可能还没被计算过。题目虽然不限制你用什么顺序遍历只要保证每个格子计算时依赖值已经算出来常规的从上到下、从左到右就行。别在双重循环里把内外层写颠倒。5. 同类题目与进阶思路5.1 一维版本乘积最大子数组这道题的一维版本就是“乘积最大子数组”。在一维连续子数组里同样要维护 preMax 和 preMin因为当前元素是负数时preMin 反而有机会成为 preMax。理解二维版本之前先把一维版本吃透你会更快形成条件反射看到乘法 DP默认双状态。5.2 如果题目要求输出对应的路径有些变体会问你最大非负积对应的路径是什么这时候单纯存一个数不够你得额外记录每个格子来自哪一个方向。可以用一个 direction 数组在 dpMax 更新时记录来源方向最后从终点回溯到起点。要注意的是因为 dpMax 和 dpMin 都可能参与最终最优路径的构成回溯时如果只存 dpMax 的更新来源得到的可能不是正确的完整路径。你需要结合最终 dpMax 值从终点往前反推每一步这一步候选值必须满足从上一步到当前格子的乘积等于当前 dpMax。如果有多个前驱满足随便选一个即可。5.3 变形统计非负积路径的数量既然有了最大非负积自然可以问一共有多少条路径的乘积是非负的这个变体就更复杂了因为它不仅要统计符号状态还要在乘法过程中保留符号分类甚至在计数时需要处理取模。思路依然是双状态用 dpPos 和 dpNeg 分别表示到达当前格子时乘积为正和乘积为负的路径数量。转移时看当前格子的值是正、负还是零。如果为零乘积只会变成零这个格子本身对符号没有贡献。这类变体的价值在于它把“双状态”从数值维护扩展到了计数维护。你一旦能理解为什么 pos 和 neg 要分开再看很多金融或概率模型里的正负状态 Markov 链思路也是相通的。5.4 拓展思考如果每一步可以选择“交换符号”怎么办有同学会想到一个改动允许在经过某个格子前把乘积的符号翻转一次。这种题如果加上操作次数限制就是典型的“带状态展开的 DP”在 dpMax 和 dpMin 基础上再增加一维 k表示已经用了多少次翻转操作。本质上是在说当你发现两个状态不够用时第三个维度就自然出现了。这就是动态规划里的“状态升维”问题LeetCode 1594 是第一次帮你打开这个思路的钥匙。我自己一开始做这题的时候用的是单 dp 数组样例过了提交之后错得莫名其妙。后来把官方例子一步步手推一遍才发现最小值状态永远是下一步翻盘的关键。从那以后凡是在乘除法的场景里看到“最大值”“最小乘积”“非负”这些关键词我都会先问自己一句是否存在负负得正的空间只要有就一定是双状态或者多状态。这个思维模型比会做这一道题更重要。