看到 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。如果只看最大值 10，10 乘上 -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 吧。结果第一行如果遇到负数，别人把你第一行的最大值和最小值都初始成了 0，0 乘上任何数都是 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] = 1，dpMin[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] = 4，dpMin[1][1] = -2。
继续算，最后右下角的 dpMax 会得到 8，dpMin 会得到一个负数。8 就是所有路径里的最大非负乘积。这个例子也说明了如果你只保留最大值，第二行第二列的时候你拿的是 1，乘上 -2 得到 -2，后面就会一路错下去；只有同时保留最小值 -2 和 4，才能在下一轮遇到负数时把局势扳回来。
3.3 关于取模和数值溢出，这里要单独聊
题目里有个很容易被误解的点：求的是“真实最大非负乘积”的模，不是“模意义下最大的乘积”。这两个概念不一样。
加法场景里，如果每一步都对 10^9 + 7 取模，不会影响大小比较，因为加法模运算保持大小关系。但乘法场景里不是这样。举个抽象例子，假设真实值 A 大于真实值 B，但 A 取模后反而小于 B 取模后。如果你在中间状态就取模，dpMax 存的就不再是真实最大值，后续所有转移都会失真。
所以正确做法是：在 DP 全过程中保留完整的大整数，只在最后返回时取模。Python 的 int 天然支持任意精度，直接这么写就行。用 C++ 或 Java 的话，如果乘积可能超过 long，但要符合 10^9+7 的取模要求，就得用 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 仍然是 1，dpMax 是 -2 乘 -2 = 4，马上就对了。
这类错误属于“状态建模不全”，不是边界写错，所以要回看状态定义和转移方程。
4.2 第一行第一列初始化为 0
有些解法用 0 填充两个 DP 数组，结果第一行或第一列有负数时，全部乘积被 0 覆盖。比如 grid[0][1] = -5，如果 dpMax[0][0] 是 1，dpMax[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 数组，样例过了，提交之后错得莫名其妙。后来把官方例子一步步手推一遍才发现，最小值状态永远是下一步翻盘的关键。从那以后，凡是在乘除法的场景里看到“最大值”“最小乘积”“非负”这些关键词，我都会先问自己一句：是否存在负负得正的空间？只要有，就一定是双状态或者多状态。这个思维模型，比会做这一道题更重要。
