1. 题目解读与核心思路LeetCode 1594 矩阵的最大非负积 是一道标着中等难度、但实际做起来挺有嚼头的动态规划题。它给出的场景很直接有一个 m x n 的矩阵从左上角出发每次只能向右或向下移动走到右下角把路径上经过的所有格子里的数字乘起来得到一个积。题目要的不是能不能走通而是在所有可行路径里找出那个最大的非负积。如果不管怎么走最终乘积都是负数那就返回 -1。我第一次看到这道题时第一反应是这还不简单直接按照路径累乘每一步都取大的最后结果不就是最大的结果一写就发现不对——因为乘法不是加法负负得正这个性质会让每一步贪心选最大彻底失效。比如某一步出现负数本来较小的负数乘上另一个负数反而能得到更大的正数反过来本来较大的正数乘上一个负数可能会让你掉进负数的坑里。所以这道题真正的核心考点不是你会不会动态规划而是你敢不敢在状态里同时维护最大和最小值。更准确地说要用两个 DP 表或者一个表里存两个值一路同时记录到达每个格子时的最大乘积和最小乘积。这一步想通了代码反而很短想不通容易被负数的符号翻转坑到怀疑人生。另外还有两个细节容易被忽略路径乘积的范围可能很大行列最多 15但数字范围是 -9 到 9极端情况下 10^4 级别虽然没到溢出级别但思维上要清楚不需要取模直接存 long long 更稳妥。非负积指的是最终乘积 0。如果所有路径的乘积都是负数才返回 -1。注意 0 是非负数所以只要路径上有个 0最后乘积一定是 0这就算非负。这道题非常适合用来巩固一个动态规划的经典思想状态里存储的信息要足够支撑未来决策符号翻转意味着只存最优值不够必须存候选极值对。明白了这一点以后遇到类似最大乘积子数组、最大最小交替的问题都会有种豁然开朗的感觉。2. 为什么不能用贪心选最大一个反例彻底讲透先说结论这道题不能用走到每一步都选乘积更大的路径这种贪心思路。原因藏在负数乘法的符号翻转里。我用一个具体例子来说明。假设有一个 2x2 的矩阵1 -2 -3 -4找一下所有路径路径 1右-下也就是 1 x (-2) x (-4) 8路径 2下-右也就是 1 x (-3) x (-4) 12最终最大乘积是 12取的是路径 2。但是如果我们用贪心从 (0,0) 出发向右走得到 -2向下走得到 -3显然 -2 大于 -3贪心会先向右走到 -2然后只能向下走到 -4最后得到 8。这个结果小于 12说明贪心错了。再换一个更微妙的例子1 -10 1 1 -1 1从左上走到右下假设到中间某一步你手上有一个 最大乘积 6 和 最小乘积 -6。接下来的数字如果是 -2那么最大 6 x (-2) -12新的最小值最小 -6 x (-2) 12新的最大值看到了吗最大和最小在符号翻转的一瞬间互换了身份。如果之前只存了最大而丢了最小这一步就会丢掉 12 这个真正的最大结果。这就是为什么必须同时维护这两个量。把这个道理说得再直白一点在加法动态规划里我只关心当前最优就够因为加上一个正数大的永远更大但在乘法里一个负数会把所有东西都反转这时候曾经最小的反而可能是未来最大的的种子。正因为这种符号翻转这道题的 DP 状态定义要做到位dpMax[i][j]表示从起点走到(i, j)的所有路径中乘积的最大值dpMin[i][j]表示从起点走到(i, j)的所有路径中乘积的最小值。两个一起转移缺一不可。3. 核心细节解析与状态转移3.1 状态定义与转移方程我们定义两个同尺寸的二维数组dpMax[i][j] 到达 (i,j) 时的最大路径乘积 dpMin[i][j] 到达 (i,j) 时的最小路径乘积起点位置也就是(0,0)处最大值和最小值都等于矩阵第一个数本身dpMax[0][0] dpMin[0][0] grid[0][0]对于每个格子(i,j)如果不是起点它只能从上方(i-1,j)或者左方(i,j-1)过来。假设当前格子值为v grid[i][j]那么能转移到当前格子的候选乘积包括四种dpMax[i-1][j] * v来自上方最大乘上当前值dpMin[i-1][j] * v来自上方最小乘上当前值dpMax[i][j-1] * v来自左方最大乘上当前值dpMin[i][j-1] * v来自左方最小乘上当前值取这四个值中的最大值作为新的dpMax[i][j]最小值作为新的dpMin[i][j]。用公式表达就是dpMax[i][j] max(dpMax[i-1][j]*v, dpMin[i-1][j]*v, dpMax[i][j-1]*v, dpMin[i][j-1]*v) dpMin[i][j] min(dpMax[i-1][j]*v, dpMin[i-1][j]*v, dpMax[i][j-1]*v, dpMin[i][j-1]*v)有些同学可能会问为什么不直接对 dpMax 和 dpMin 取 max为什么要四个一起算因为当前值v可能是正数、负数或 0。如果是正数最大乘正数仍是最大最小乘正数仍是最小看起来只需要dpMax * v和dpMin * v就行但如果v是负数最大乘负数变成最小最小乘负数变成最大这时候必须用dpMin去更新dpMax。四个一起算就不用分类讨论了代码更简洁也不容易漏。再说边界条件。第一行只能从左边过来第一列只能从上边过来。我习惯把两个表初始化成比较大的正数和比较小的负数比如LONG_MIN和LONG_MAX这样边界的无效状态不会干扰转移或者更简单地单独处理第一行和第一列。我比较推荐初始化为极值法写起来不容易乱也方便后面统一转移。3.2 为什么用 long long 而不是 int还是那句老话LeetCode 的很多题目时间和空间复杂度是考核重点但乘积溢出经常被忽略。这道题虽然 m、n 最大 15看起来不大但极端情况比如全是 9 的矩阵路径上有 29 个格子15 行 15 列的话实际走 29 步算上起点共 29 个元素9^29 是个天文数字。虽然题目的测试用例不会真的弄到溢出但用 int 心里不踏实而且万一以后题目数据变了int 就可能翻车。直接用 long long省心。另外还有一点最终积可能很大LeetCode 本身要求返回int但中间过程用 long long 是允许的最后强转回 int 即可。3.3 空间优化滚动数组思路这道题可以用一维滚动数组把空间复杂度从 O(mn) 降到 O(n)。做法是每处理一行时用一个长度为 n 的数组dpMax和dpMin在处理第i行第j列时dpMax[j]在更新之前保存的是上一行第i-1行第j列的值dpMax[j-1]在当前行已经更新过保存的是当前行第j-1列的值。于是转移时就变成了dpMax[j] max(dpMax[j]*v, dpMin[j]*v, dpMax[j-1]*v, dpMin[j-1]*v) dpMin[j] min(dpMax[j]*v, dpMin[j]*v, dpMax[j-1]*v, dpMin[j-1]*v)注意这里的dpMax[j]*v和dpMin[j]*v使用的都是旧值也就是上一行的结果而dpMax[j-1]和dpMin[j-1]是新值也就是当前行左边格子的结果。由于乘法和赋值是分开的需要小心先用临时变量保存旧值再赋值不然更新dpMax[j]后再去取dpMin[j]值已经变了。我个人在实践中一般先不做滚动优化先把二维的写对、跑通再考虑压缩。因为这道题核心难点不在空间而在状态设计。先把二维版本跑通逻辑验证没问题再改滚动数组既保险又能加深理解。4. 实操过程与核心环节实现4.1 完整代码实现C下面给出一版完整的 C 实现包含二维 DP 和滚动数组两种写法。先看二维版本class Solution { public: int maxProductPath(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); // 用 long long 存防止中间乘积溢出 vectorvectorlong long dpMax(m, vectorlong long(n)); vectorvectorlong long dpMin(m, vectorlong long(n)); dpMax[0][0] dpMin[0][0] grid[0][0]; // 初始化第一行 for (int j 1; j n; j) { long long v grid[0][j]; dpMax[0][j] dpMax[0][j-1] * v; dpMin[0][j] dpMin[0][j-1] * v; } // 初始化第一列 for (int i 1; i m; i) { long long v grid[i][0]; dpMax[i][0] dpMax[i-1][0] * v; dpMin[i][0] dpMin[i-1][0] * v; } for (int i 1; i m; i) { for (int j 1; j n; j) { long long v grid[i][j]; // 四个候选值 long long candidates[4] { dpMax[i-1][j] * v, dpMin[i-1][j] * v, dpMax[i][j-1] * v, dpMin[i][j-1] * v }; dpMax[i][j] *max_element(candidates, candidates 4); dpMin[i][j] *min_element(candidates, candidates 4); } } long long ans dpMax[m-1][n-1]; return ans 0 ? (int)ans : -1; } };再看滚动数组版本class Solution { public: int maxProductPath(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); vectorlong long dpMax(n); vectorlong long dpMin(n); // 处理起点 dpMax[0] dpMin[0] grid[0][0]; // 处理第一行 for (int j 1; j n; j) { long long v grid[0][j]; dpMax[j] dpMax[j-1] * v; dpMin[j] dpMin[j-1] * v; } for (int i 1; i m; i) { for (int j 0; j n; j) { long long v grid[i][j]; if (j 0) { // 第一列只能从上方下来 dpMax[0] dpMax[0] * v; dpMin[0] dpMin[0] * v; } else { // 旧值上一行的当前列 long long upMax dpMax[j]; long long upMin dpMin[j]; // 新值当前行的左边列 long long leftMax dpMax[j-1]; long long leftMin dpMin[j-1]; long long a upMax * v; long long b upMin * v; long long c leftMax * v; long long d leftMin * v; dpMax[j] max(max(a, b), max(c, d)); dpMin[j] min(min(a, b), min(c, d)); } } } return dpMax[n-1] 0 ? (int)dpMax[n-1] : -1; } };多说一句滚动数组版本里第一列的处理要单独拿出来因为j0时dpMax[j-1]越界了而且第一列只能从上方更新。代码里我用了upMax、upMin临时变量保存旧值避免更新dpMax[j]后被后面的dpMin[j]取到新值。这是滚动数组最容易踩的坑。4.2 为什么max/min要比较四个数而不是两个数有同学可能会想反正dpMax就是最大值dpMin就是最小值那更新时用max(dpMax 的候选们)不就行了吗但最大值乘当前值和最小值乘当前值谁是最终的最大完全取决于当前值的正负。举例dpMax[i-1][j] 10 dpMin[i-1][j] -10 v -2只算dpMax[i-1][j] * v -20dpMin[i-1][j] * v 20很明显最大值 20 来自最小值乘负数。如果不看dpMin就漏了。所以统一比较四个候选值是最稳妥的不需要判断v的符号分类讨论少了代码 bug 也少了。4.3 边界条件为什么要单独处理二维 DP 里第一行的格子只能从左过来第一列的格子只能从上过来。我用循环单独处理逻辑清晰。但还有个小细节如果m 1且n 1也就是矩阵只有一个格子那么起点就是终点。此时dpMax[0][0] grid[0][0]答案就是该格子本身。若它是负数所有路径乘积就是负数返回 -1若它是 0 或正数直接返回本身。这个边界情况千万别漏。滚动数组版同样要处理n 1的情况此时只有一列每行都只能从上方走不需要j-1的逻辑。5. 常见问题与排查技巧实录5.1 为什么我返回了负数但预期答案是 0很大概率是没有正确处理 0。题目要求的是最大非负积也就是说如果存在一条路径乘积为 0那么 0 就是候选答案。有些同学在 DP 转移时用0初始化 dp 数组导致负数乘正数的地方全被 0 覆盖了。比如dpMax[i][j] max(dpMax[i][j], ...)这样写如果dpMax[i][j]默认是 0那么遇到负数乘积时max会保留 0导致负数永远无法被记录。而实际上负数路径虽然最后可能是负数但负数乘负数可能变正必须保留所有真实候选值。解决方法是不要用 0 初始化 DP 数组第一行/第一列直接乘算其余格子用四个候选值实时计算或者初始化为LONG_MIN/LONG_MAX再配合更新。5.2 为什么最大值算出来比预期大很多是因为 int 溢出吗一般是溢出。比如中间结果可能达到 9^29远超 int 范围。我在开发中遇到过一次最大值莫名变成了负数排查半天才发现是 int 溢出。解决方案用long long这是最稳妥的。如果题目要求返回 int可以在最后强转但中间过程一定不能用 int。5.3 滚动数组版本为什么结果不对明明二维版本是正确的滚动数组容易出现两个问题覆盖顺序问题dpMax[j]和dpMin[j]更新之后如果下一格j1需要使用旧的dpMax[j]但实际上j已经被覆盖导致结果错误。第一列处理不当j0时不能引用j-1要单独处理。我之前踩过一次坑循环里先把dpMax[j]更新了然后下一轮dpMax[j1]取的是新的dpMax[j]原本应该是上一行的旧值结果用了当前行的新值答案自然不对。后来我固定了一个习惯在for循环内部先把需要的旧值全部用临时变量存下来再计算新值这样无论顺序怎么变都不会错。5.4 边界情况全汇总情况处理方式矩阵只有一个格子返回该格子值0 原值0 则 -1只有一行只能一直往右走乘积就是一行元素的累乘只有一列只能一直往下走乘积就是一列元素的累乘格子值含 00 参与乘积后结果必为 00 是非负数可以作为答案候选最大乘积为负数返回 -1说明没有任何路径是非负积5.5 自测用例推荐我每次写完这类 DP 题都会跑几个反例强烈建议你也试试用例1 [[1, -2, 3], [4, -5, 6], [-7, 8, -9]]这个用例里有正有负有大有小能测试符号翻转和边界混合。跑出来最终答案应该是 630路径是 1 - 4 - -5 - 8 - -9不对这条路乘积是 -1440正确的路径是 1 - -2 - 3 - 6 - -9 324也不对。反正这种混合用例最好别手算直接跑代码对比只要能通过标准测试再配合几个小用例就有信心。用例2 [[0, -1], [1, -1]]路径有两条0 x -1 x -1 0以及 0 x 1 x -1 0。最终答案 0不是 -1。这个用例专门验证0 是非负的这个点。用例3 [[-1, -2], [-4, -3]]所有路径乘积均为正数。其中 1 条-1 x -2 x -3 -6另一条-1 x -4 x -3 -12不对两条都是负数? 等等-1 x -2 22 x -3 -6-1 x -4 44 x -3 -12全都是负数所以答案是 -1。这个用例验证了不存在非负积时的返回值。5.6 动态规划中的常见思维盲区再补充一个很重要的盲区很多人会以为最大和最小是两个独立的状态但实际上它们彼此依赖。因为同一个路径上最大和最小可能来自不同的路径但它们必须被同时保留。比如某个格子的最大乘积来自上方路径 A最小乘积来自上方路径 B下一格乘一个负数后路径 A 变成最小路径 B 变成最大。如果只保存最大不保存最小B 就被丢掉了。这正是这道题的精髓。所以以后做最大乘积子数组、除法类 DP、有符号翻转的 DP时都要养成同时维护 max 和 min 的习惯。这是这一系列问题的通解不局限在这个题目里。6. 实操心得与小技巧总结这类矩阵 DP 的题我最想分享的心得是先把状态定义写清楚再动手写代码。很多同学一上来就开始写转移方程写着写着发现漏了情况回头再补改来改去浪费时间。我自己的习惯是先在纸上画一个小矩阵手写出状态dpMax、dpMin。用肉眼追踪一遍样例路径确认什么时候需要用到 dpMin 的值。再写代码第一版直接用二维数组不搞滚动保证正确性。测试通过后再考虑空间优化。此外还有几个细节判断正负时不要写成ans 0因为 0 是非负要写成ans 0。取模运算这里不需要题目没要求别自己画蛇添足。grid数值范围是 -9 到 9所以乘积符号翻转是必然发生的不要抱侥幸心理一定要把 dpMin 的作用发挥出来。最后再分享一个小技巧如果面试或笔试时遇到类似的题目可以在分析阶段先问自己一个问题如果当前操作是加法一维 DP 就够如果是乘法那就要考虑正负号翻转一维不够就要考虑二维状态。 这个判断框架能帮你在 30 秒内确定正确的 DP 方向避免在错误道路上越走越远。LeetCode 1594 这道题其实不算难但它把乘法 DP 中 max 和 min 必须并列的思想体现得淋漓尽致。把这道题吃透再去做最大乘积子数组、最大子数组和与负数的纠缠都会轻松不少。建议你亲手把二维版本和滚动数组版本各写一遍再用上面的自测用例跑一遍相信你能感受到这种状态设计的巧妙之处。 
长河君 · 2026/10/16 12:36:31 · 阅读 1.2k LeetCode 1594 矩阵最大非负积：动态规划中最大最小状态同维护
1. 题目解读与核心思路LeetCode 1594 矩阵的最大非负积 是一道标着中等难度、但实际做起来挺有嚼头的动态规划题。它给出的场景很直接有一个 m x n 的矩阵从左上角出发每次只能向右或向下移动走到右下角把路径上经过的所有格子里的数字乘起来得到一个积。题目要的不是能不能走通而是在所有可行路径里找出那个最大的非负积。如果不管怎么走最终乘积都是负数那就返回 -1。我第一次看到这道题时第一反应是这还不简单直接按照路径累乘每一步都取大的最后结果不就是最大的结果一写就发现不对——因为乘法不是加法负负得正这个性质会让每一步贪心选最大彻底失效。比如某一步出现负数本来较小的负数乘上另一个负数反而能得到更大的正数反过来本来较大的正数乘上一个负数可能会让你掉进负数的坑里。所以这道题真正的核心考点不是你会不会动态规划而是你敢不敢在状态里同时维护最大和最小值。更准确地说要用两个 DP 表或者一个表里存两个值一路同时记录到达每个格子时的最大乘积和最小乘积。这一步想通了代码反而很短想不通容易被负数的符号翻转坑到怀疑人生。另外还有两个细节容易被忽略路径乘积的范围可能很大行列最多 15但数字范围是 -9 到 9极端情况下 10^4 级别虽然没到溢出级别但思维上要清楚不需要取模直接存 long long 更稳妥。非负积指的是最终乘积 0。如果所有路径的乘积都是负数才返回 -1。注意 0 是非负数所以只要路径上有个 0最后乘积一定是 0这就算非负。这道题非常适合用来巩固一个动态规划的经典思想状态里存储的信息要足够支撑未来决策符号翻转意味着只存最优值不够必须存候选极值对。明白了这一点以后遇到类似最大乘积子数组、最大最小交替的问题都会有种豁然开朗的感觉。2. 为什么不能用贪心选最大一个反例彻底讲透先说结论这道题不能用走到每一步都选乘积更大的路径这种贪心思路。原因藏在负数乘法的符号翻转里。我用一个具体例子来说明。假设有一个 2x2 的矩阵1 -2 -3 -4找一下所有路径路径 1右-下也就是 1 x (-2) x (-4) 8路径 2下-右也就是 1 x (-3) x (-4) 12最终最大乘积是 12取的是路径 2。但是如果我们用贪心从 (0,0) 出发向右走得到 -2向下走得到 -3显然 -2 大于 -3贪心会先向右走到 -2然后只能向下走到 -4最后得到 8。这个结果小于 12说明贪心错了。再换一个更微妙的例子1 -10 1 1 -1 1从左上走到右下假设到中间某一步你手上有一个 最大乘积 6 和 最小乘积 -6。接下来的数字如果是 -2那么最大 6 x (-2) -12新的最小值最小 -6 x (-2) 12新的最大值看到了吗最大和最小在符号翻转的一瞬间互换了身份。如果之前只存了最大而丢了最小这一步就会丢掉 12 这个真正的最大结果。这就是为什么必须同时维护这两个量。把这个道理说得再直白一点在加法动态规划里我只关心当前最优就够因为加上一个正数大的永远更大但在乘法里一个负数会把所有东西都反转这时候曾经最小的反而可能是未来最大的的种子。正因为这种符号翻转这道题的 DP 状态定义要做到位dpMax[i][j]表示从起点走到(i, j)的所有路径中乘积的最大值dpMin[i][j]表示从起点走到(i, j)的所有路径中乘积的最小值。两个一起转移缺一不可。3. 核心细节解析与状态转移3.1 状态定义与转移方程我们定义两个同尺寸的二维数组dpMax[i][j] 到达 (i,j) 时的最大路径乘积 dpMin[i][j] 到达 (i,j) 时的最小路径乘积起点位置也就是(0,0)处最大值和最小值都等于矩阵第一个数本身dpMax[0][0] dpMin[0][0] grid[0][0]对于每个格子(i,j)如果不是起点它只能从上方(i-1,j)或者左方(i,j-1)过来。假设当前格子值为v grid[i][j]那么能转移到当前格子的候选乘积包括四种dpMax[i-1][j] * v来自上方最大乘上当前值dpMin[i-1][j] * v来自上方最小乘上当前值dpMax[i][j-1] * v来自左方最大乘上当前值dpMin[i][j-1] * v来自左方最小乘上当前值取这四个值中的最大值作为新的dpMax[i][j]最小值作为新的dpMin[i][j]。用公式表达就是dpMax[i][j] max(dpMax[i-1][j]*v, dpMin[i-1][j]*v, dpMax[i][j-1]*v, dpMin[i][j-1]*v) dpMin[i][j] min(dpMax[i-1][j]*v, dpMin[i-1][j]*v, dpMax[i][j-1]*v, dpMin[i][j-1]*v)有些同学可能会问为什么不直接对 dpMax 和 dpMin 取 max为什么要四个一起算因为当前值v可能是正数、负数或 0。如果是正数最大乘正数仍是最大最小乘正数仍是最小看起来只需要dpMax * v和dpMin * v就行但如果v是负数最大乘负数变成最小最小乘负数变成最大这时候必须用dpMin去更新dpMax。四个一起算就不用分类讨论了代码更简洁也不容易漏。再说边界条件。第一行只能从左边过来第一列只能从上边过来。我习惯把两个表初始化成比较大的正数和比较小的负数比如LONG_MIN和LONG_MAX这样边界的无效状态不会干扰转移或者更简单地单独处理第一行和第一列。我比较推荐初始化为极值法写起来不容易乱也方便后面统一转移。3.2 为什么用 long long 而不是 int还是那句老话LeetCode 的很多题目时间和空间复杂度是考核重点但乘积溢出经常被忽略。这道题虽然 m、n 最大 15看起来不大但极端情况比如全是 9 的矩阵路径上有 29 个格子15 行 15 列的话实际走 29 步算上起点共 29 个元素9^29 是个天文数字。虽然题目的测试用例不会真的弄到溢出但用 int 心里不踏实而且万一以后题目数据变了int 就可能翻车。直接用 long long省心。另外还有一点最终积可能很大LeetCode 本身要求返回int但中间过程用 long long 是允许的最后强转回 int 即可。3.3 空间优化滚动数组思路这道题可以用一维滚动数组把空间复杂度从 O(mn) 降到 O(n)。做法是每处理一行时用一个长度为 n 的数组dpMax和dpMin在处理第i行第j列时dpMax[j]在更新之前保存的是上一行第i-1行第j列的值dpMax[j-1]在当前行已经更新过保存的是当前行第j-1列的值。于是转移时就变成了dpMax[j] max(dpMax[j]*v, dpMin[j]*v, dpMax[j-1]*v, dpMin[j-1]*v) dpMin[j] min(dpMax[j]*v, dpMin[j]*v, dpMax[j-1]*v, dpMin[j-1]*v)注意这里的dpMax[j]*v和dpMin[j]*v使用的都是旧值也就是上一行的结果而dpMax[j-1]和dpMin[j-1]是新值也就是当前行左边格子的结果。由于乘法和赋值是分开的需要小心先用临时变量保存旧值再赋值不然更新dpMax[j]后再去取dpMin[j]值已经变了。我个人在实践中一般先不做滚动优化先把二维的写对、跑通再考虑压缩。因为这道题核心难点不在空间而在状态设计。先把二维版本跑通逻辑验证没问题再改滚动数组既保险又能加深理解。4. 实操过程与核心环节实现4.1 完整代码实现C下面给出一版完整的 C 实现包含二维 DP 和滚动数组两种写法。先看二维版本class Solution { public: int maxProductPath(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); // 用 long long 存防止中间乘积溢出 vectorvectorlong long dpMax(m, vectorlong long(n)); vectorvectorlong long dpMin(m, vectorlong long(n)); dpMax[0][0] dpMin[0][0] grid[0][0]; // 初始化第一行 for (int j 1; j n; j) { long long v grid[0][j]; dpMax[0][j] dpMax[0][j-1] * v; dpMin[0][j] dpMin[0][j-1] * v; } // 初始化第一列 for (int i 1; i m; i) { long long v grid[i][0]; dpMax[i][0] dpMax[i-1][0] * v; dpMin[i][0] dpMin[i-1][0] * v; } for (int i 1; i m; i) { for (int j 1; j n; j) { long long v grid[i][j]; // 四个候选值 long long candidates[4] { dpMax[i-1][j] * v, dpMin[i-1][j] * v, dpMax[i][j-1] * v, dpMin[i][j-1] * v }; dpMax[i][j] *max_element(candidates, candidates 4); dpMin[i][j] *min_element(candidates, candidates 4); } } long long ans dpMax[m-1][n-1]; return ans 0 ? (int)ans : -1; } };再看滚动数组版本class Solution { public: int maxProductPath(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); vectorlong long dpMax(n); vectorlong long dpMin(n); // 处理起点 dpMax[0] dpMin[0] grid[0][0]; // 处理第一行 for (int j 1; j n; j) { long long v grid[0][j]; dpMax[j] dpMax[j-1] * v; dpMin[j] dpMin[j-1] * v; } for (int i 1; i m; i) { for (int j 0; j n; j) { long long v grid[i][j]; if (j 0) { // 第一列只能从上方下来 dpMax[0] dpMax[0] * v; dpMin[0] dpMin[0] * v; } else { // 旧值上一行的当前列 long long upMax dpMax[j]; long long upMin dpMin[j]; // 新值当前行的左边列 long long leftMax dpMax[j-1]; long long leftMin dpMin[j-1]; long long a upMax * v; long long b upMin * v; long long c leftMax * v; long long d leftMin * v; dpMax[j] max(max(a, b), max(c, d)); dpMin[j] min(min(a, b), min(c, d)); } } } return dpMax[n-1] 0 ? (int)dpMax[n-1] : -1; } };多说一句滚动数组版本里第一列的处理要单独拿出来因为j0时dpMax[j-1]越界了而且第一列只能从上方更新。代码里我用了upMax、upMin临时变量保存旧值避免更新dpMax[j]后被后面的dpMin[j]取到新值。这是滚动数组最容易踩的坑。4.2 为什么max/min要比较四个数而不是两个数有同学可能会想反正dpMax就是最大值dpMin就是最小值那更新时用max(dpMax 的候选们)不就行了吗但最大值乘当前值和最小值乘当前值谁是最终的最大完全取决于当前值的正负。举例dpMax[i-1][j] 10 dpMin[i-1][j] -10 v -2只算dpMax[i-1][j] * v -20dpMin[i-1][j] * v 20很明显最大值 20 来自最小值乘负数。如果不看dpMin就漏了。所以统一比较四个候选值是最稳妥的不需要判断v的符号分类讨论少了代码 bug 也少了。4.3 边界条件为什么要单独处理二维 DP 里第一行的格子只能从左过来第一列的格子只能从上过来。我用循环单独处理逻辑清晰。但还有个小细节如果m 1且n 1也就是矩阵只有一个格子那么起点就是终点。此时dpMax[0][0] grid[0][0]答案就是该格子本身。若它是负数所有路径乘积就是负数返回 -1若它是 0 或正数直接返回本身。这个边界情况千万别漏。滚动数组版同样要处理n 1的情况此时只有一列每行都只能从上方走不需要j-1的逻辑。5. 常见问题与排查技巧实录5.1 为什么我返回了负数但预期答案是 0很大概率是没有正确处理 0。题目要求的是最大非负积也就是说如果存在一条路径乘积为 0那么 0 就是候选答案。有些同学在 DP 转移时用0初始化 dp 数组导致负数乘正数的地方全被 0 覆盖了。比如dpMax[i][j] max(dpMax[i][j], ...)这样写如果dpMax[i][j]默认是 0那么遇到负数乘积时max会保留 0导致负数永远无法被记录。而实际上负数路径虽然最后可能是负数但负数乘负数可能变正必须保留所有真实候选值。解决方法是不要用 0 初始化 DP 数组第一行/第一列直接乘算其余格子用四个候选值实时计算或者初始化为LONG_MIN/LONG_MAX再配合更新。5.2 为什么最大值算出来比预期大很多是因为 int 溢出吗一般是溢出。比如中间结果可能达到 9^29远超 int 范围。我在开发中遇到过一次最大值莫名变成了负数排查半天才发现是 int 溢出。解决方案用long long这是最稳妥的。如果题目要求返回 int可以在最后强转但中间过程一定不能用 int。5.3 滚动数组版本为什么结果不对明明二维版本是正确的滚动数组容易出现两个问题覆盖顺序问题dpMax[j]和dpMin[j]更新之后如果下一格j1需要使用旧的dpMax[j]但实际上j已经被覆盖导致结果错误。第一列处理不当j0时不能引用j-1要单独处理。我之前踩过一次坑循环里先把dpMax[j]更新了然后下一轮dpMax[j1]取的是新的dpMax[j]原本应该是上一行的旧值结果用了当前行的新值答案自然不对。后来我固定了一个习惯在for循环内部先把需要的旧值全部用临时变量存下来再计算新值这样无论顺序怎么变都不会错。5.4 边界情况全汇总情况处理方式矩阵只有一个格子返回该格子值0 原值0 则 -1只有一行只能一直往右走乘积就是一行元素的累乘只有一列只能一直往下走乘积就是一列元素的累乘格子值含 00 参与乘积后结果必为 00 是非负数可以作为答案候选最大乘积为负数返回 -1说明没有任何路径是非负积5.5 自测用例推荐我每次写完这类 DP 题都会跑几个反例强烈建议你也试试用例1 [[1, -2, 3], [4, -5, 6], [-7, 8, -9]]这个用例里有正有负有大有小能测试符号翻转和边界混合。跑出来最终答案应该是 630路径是 1 - 4 - -5 - 8 - -9不对这条路乘积是 -1440正确的路径是 1 - -2 - 3 - 6 - -9 324也不对。反正这种混合用例最好别手算直接跑代码对比只要能通过标准测试再配合几个小用例就有信心。用例2 [[0, -1], [1, -1]]路径有两条0 x -1 x -1 0以及 0 x 1 x -1 0。最终答案 0不是 -1。这个用例专门验证0 是非负的这个点。用例3 [[-1, -2], [-4, -3]]所有路径乘积均为正数。其中 1 条-1 x -2 x -3 -6另一条-1 x -4 x -3 -12不对两条都是负数? 等等-1 x -2 22 x -3 -6-1 x -4 44 x -3 -12全都是负数所以答案是 -1。这个用例验证了不存在非负积时的返回值。5.6 动态规划中的常见思维盲区再补充一个很重要的盲区很多人会以为最大和最小是两个独立的状态但实际上它们彼此依赖。因为同一个路径上最大和最小可能来自不同的路径但它们必须被同时保留。比如某个格子的最大乘积来自上方路径 A最小乘积来自上方路径 B下一格乘一个负数后路径 A 变成最小路径 B 变成最大。如果只保存最大不保存最小B 就被丢掉了。这正是这道题的精髓。所以以后做最大乘积子数组、除法类 DP、有符号翻转的 DP时都要养成同时维护 max 和 min 的习惯。这是这一系列问题的通解不局限在这个题目里。6. 实操心得与小技巧总结这类矩阵 DP 的题我最想分享的心得是先把状态定义写清楚再动手写代码。很多同学一上来就开始写转移方程写着写着发现漏了情况回头再补改来改去浪费时间。我自己的习惯是先在纸上画一个小矩阵手写出状态dpMax、dpMin。用肉眼追踪一遍样例路径确认什么时候需要用到 dpMin 的值。再写代码第一版直接用二维数组不搞滚动保证正确性。测试通过后再考虑空间优化。此外还有几个细节判断正负时不要写成ans 0因为 0 是非负要写成ans 0。取模运算这里不需要题目没要求别自己画蛇添足。grid数值范围是 -9 到 9所以乘积符号翻转是必然发生的不要抱侥幸心理一定要把 dpMin 的作用发挥出来。最后再分享一个小技巧如果面试或笔试时遇到类似的题目可以在分析阶段先问自己一个问题如果当前操作是加法一维 DP 就够如果是乘法那就要考虑正负号翻转一维不够就要考虑二维状态。 这个判断框架能帮你在 30 秒内确定正确的 DP 方向避免在错误道路上越走越远。LeetCode 1594 这道题其实不算难但它把乘法 DP 中 max 和 min 必须并列的思想体现得淋漓尽致。把这道题吃透再去做最大乘积子数组、最大子数组和与负数的纠缠都会轻松不少。建议你亲手把二维版本和滚动数组版本各写一遍再用上面的自测用例跑一遍相信你能感受到这种状态设计的巧妙之处。