做了这么多年LeetCode我有个习惯遇到“中等”难度的矩阵DP题先不急着看题解自己推一遍状态转移方程。因为很多中等题其实是“纸老虎”难点不在算法本身而在状态设计是否周全。**LeetCode 1594“矩阵的最大非负积”**就是很典型的一道——它表面是个乘积DP实际考察的是“负负得正”这个初中数学常识能不能被翻译成状态转移逻辑。今天这篇文章我想用记忆化搜索、递推和空间优化三条路线完整拆解这道题把每一步推导和踩过的坑都讲清楚。先给没做过这道题的朋友交代一下背景给定一个m x n的整数矩阵grid你需要从左上角(0,0)走到右下角(m-1,n-1)每次只能向右或向下移动一步把路径经过的所有元素相乘最终目标是让这个乘积最大并且要求这道题的乘积必须是非负数。如果不存在非负的乘积路径返回-1。注意矩阵元素可能是负数、零、正数范围在[-10000, 10000]之间。题目难度标为中等但如果你想当然地只用“当前最大值”这一个状态往后推很快就会撞墙。这篇文章适合三类读者一是正在刷LeetCode周赛题目、想把DP思路理清楚的选手二是面试前想复习动态规划从递归到递推再到空间优化全流程的求职者第三类是像我一样对“状态设计”有执念、想看透每一步为什么这么写的算法爱好者。我会从最朴素的搜索开始一步步优化到只用一行数组的版本并解释每个设计背后的理由。1. 负数的存在让“最优子结构”变得不简单1.1 为什么不能只维护一个最大值状态很多同学看到这道题的第一反应是这不就是个最普通的数字三角形DP吗维护dp[i][j]表示走到(i,j)时的最大乘积然后取上边和左边两个来源的较大值再乘上当前格子的值就完事了。这个思路在矩阵元素全为正数时完全正确但一旦遇到负数问题就出现了。我们假设当前格子值grid[i][j] -2而两个来源路径的最大乘积一个是10另一个是-8。按照“只取最大值”的逻辑10 * (-2) -20另一条路(-8) * (-2) 16结果是-20我们错过了正数16。也就是说当前结果的最大值可能来自“过去的最小值”。因为负数会反转大小关系一个历史上很小的负数乘上当前这个负数后反而能变成很大的正数。这是整道题最核心、也最反直觉的地方。如果你想当然地套用“最大加最大”的直觉这道题一定做不出来。1.2 在矩阵路径问题里乘法与加法的本质差异加法路径问题里一旦某条路径的和比较小后续无论加什么都很难逆转正数情况下。但乘法不一样乘法里的负数会给整个序列带来“反转”的机会。这就像我们生活中常说的“祸兮福之所倚”——一个很“差”的状态换个条件反而变成最好的基础。所以在做状态转移设计时必须同时关注两条链最大值链和最小值链。走到每个格子时我需要知道能从左边和上边到这里的“最大乘积”和“最小乘积”。最大值可以用来迎接正数最小值则用来迎接负数。只有这两份情报都在手里才能在下一次转移时做出正确决策。这个设计思路不仅适用于这道题也适用于所有“存在负数导致符号会反转”的DP题目。它本质上是在维护两个集合分别对应“有利状态”和“不利状态”而不去主观抛弃任何一个因为你不知道后续格子是正还是负。用学术一点的话说这里的可行状态空间天然需要两部分来覆盖单一标量不足以表达完整信息。2. 状态定义的两个关键决策极值成对与初始值处理2.1dpMax和dpMin双表设计明确需要两个状态之后我先把状态定义写清楚dpMax[i][j]从(0,0)走到(i,j)的所有路径中乘积的最大值。dpMin[i][j]从(0,0)走到(i,j)的所有路径中乘积的最小值。转移时对于每一个格子(i,j)它的前驱只有两个上方的(i-1,j)和左边的(i,j-1)。对于这两个前驱我们手里分别有它们的dpMax和dpMin。于是当前格子可能出现的乘积结果一共有四个候选值dpMax[i-1][j] * grid[i][j] dpMin[i-1][j] * grid[i][j] dpMax[i][j-1] * grid[i][j] dpMin[i][j-1] * grid[i][j]把这四个值都算出来取其中的最大值作为dpMax[i][j]取最小值作为dpMin[i][j]。这个操作看起来简单但它是整道题正确性的基石——它确保我们“不遗漏任何一种符号组合”。无论grid[i][j]是正、负还是零四个候选里一定包含了能产生最终最优解的来源。2.2 初始化时最容易踩的坑第一行和第一列不能直接套公式说完状态定义初始化的问题马上浮上来。矩阵左上角dpMax[0][0]和dpMin[0][0]显然是grid[0][0]这个没争议。但第一行和第一列怎么初始化很多第一次写这道题的同学会把第一行的dpMax[0][j]直接写成dpMax[0][j-1] * grid[0][j]第一列同理。看起来没问题因为第一行只能从左边过来第一列只能从上边过来。但有一个细节如果第一行第一个出现的负数后面跟着负数这个公式依然能正确捕获符号反转吗能。因为公式里只有一个前驱dpMax和dpMin分别是同一个值所以无论什么情况都能算对。但是要注意dpMin[0][j]也要同步更新否则后面用dpMin时拿到的就是未初始化的垃圾值。这里真正隐蔽的坑是在 C 和 Java 里new int[n]默认是 0而 0 作为乘积的初始值会污染后续所有推导。比如第一行的dpMax[0][1]如果因为某种错误没有被正确计算它的 0 值会乘到后面的格子导致结果全变成 0错误还很隐蔽不易排查。我一开始写的时候也在这里栽过跟头后来索性第一行第一列全部用grid自身的累乘来初始化绝不依赖默认值。2.3 从终点反推初始答案什么时候返回 -1所有状态填完之后最终答案就存在dpMax[m-1][n-1]。但这个值有可能是负数此时按照题目要求应当返回-1。还有另一种情况矩阵里所有路径乘积都必然是负数也会让dpMax终点值为负。所以在返回之前必须做一次判断return dpMax[m-1][n-1] 0 ? dpMax[m-1][n-1] : -1;这里还有个值得注意的小坑乘积会非常大。grid值范围在[-10000, 10000]矩阵最大尺寸15 x 15极端情况下乘积数量级是10000^29早就超出int范围。所以dpMax和dpMin必须用long或long long类型否则会溢出成奇怪的值。3. 第一版递推实现清晰但空间吃紧3.1 基于双表的三层循环完整代码想清楚状态定义和初始化之后写代码就顺理成章了。我先把最基础的双二维表版本贴出来方便大家对照后面的优化版本。public int maxProductPath(int[][] grid) { int m grid.length; int n grid[0].length; long[][] dpMax new long[m][n]; long[][] dpMin new long[m][n]; dpMax[0][0] grid[0][0]; dpMin[0][0] grid[0][0]; // 初始化第一行 for (int j 1; j n; j) { dpMax[0][j] dpMax[0][j-1] * grid[0][j]; dpMin[0][j] dpMin[0][j-1] * grid[0][j]; } // 初始化第一列 for (int i 1; i m; i) { dpMax[i][0] dpMax[i-1][0] * grid[i][0]; dpMin[i][0] dpMin[i-1][0] * grid[i][0]; } // 递推填充 for (int i 1; i m; i) { for (int j 1; j n; j) { long upMax dpMax[i-1][j]; long upMin dpMin[i-1][j]; long leftMax dpMax[i][j-1]; long leftMin dpMin[i][j-1]; long candidatesMax Math.max( Math.max(upMax * grid[i][j], upMin * grid[i][j]), Math.max(leftMax * grid[i][j], leftMin * grid[i][j]) ); long candidatesMin Math.min( Math.min(upMax * grid[i][j], upMin * grid[i][j]), Math.min(leftMax * grid[i][j], leftMin * grid[i][j]) ); dpMax[i][j] candidatesMax; dpMin[i][j] candidatesMin; } } return dpMax[m-1][n-1] 0 ? (int)(dpMax[m-1][n-1]) : -1; }这段代码的复杂度是O(m*n)时间、O(m*n)空间在15 x 15的矩阵上运行毫无压力。但我做这道题时不仅满足于“能过”而是想知道能不能把空间压下来于是就有了滚动数组和一行数组的版本。3.2 为什么在15x15的小数据里也要考虑空间优化你可能会问矩阵最大就 15 x 15四个 long 数组分别才 225 个元素有必要优化吗从实用角度讲确实没必要。但 LeetCode 这种题目考察的从来不只是“能不能过”这个单一维度。面试官经常会追问“如果矩阵变成1000 x 1000呢”“如果内存限制只有 1MB 呢”这时候如果你能答出滚动数组优化思路就比只会背二维DP解法的候选人多一个加分项。而且从学习角度讲从二维到一维的优化过程正是加深对“状态依赖关系”理解的好机会。这也是我为什么坚持把空间优化版本拿出来讲——不是炫技而是让你理解 DP 的迭代方向为什么是“从左到右从上到下”。3.3 记忆化搜索为什么不是最优解但值得写递推之外另一种解法是记忆化搜索。它的思路是从终点(m-1,n-1)反向递归每次递归向左上方向探索前驱。因为状态数也就是m*n所以配合 memo 表复杂度同样是O(m*n)。理论上记忆化搜索不需要显式考虑遍历顺序因为它通过递归天然保证了依赖关系代码逻辑更贴近“人脑”思考过程不容易出错。但实际运行时递归函数调用有额外开销而且 Java 的递归深度在极端情况下还要提防栈溢出——虽然 15 层不会但如果推广到 1000 行就得小心。我的建议是理解阶段用记忆化搜索理清思路生产/竞赛阶段用递推表写空间优化后性能更有保障。4. 滚动数组优化把空间从 O(mn) 降到 O(n)4.1 观察到当前行只依赖上一行和当前行左侧如果你仔细看递推关系会发现一个事实dpMax[i][j]依赖的是上一行同列dpMax[i-1][j]和当前行左侧dpMax[i][j-1]。也就是说当我们填到第i行时所有更早的行i-2, i-3...都不会再被用到。空间可以被复用。办法很简单用两个一维数组maxRow[j]和minRow[j]来表示“当前行”的状态每次填完一行之后当前行变成下一行的“上一行”。这个技巧在动态规划里叫滚动数组本质上是用“时间换空间”的典型反面——我们保留了时间不变却把空间缩小了一个维度。4.2 一行数组的正确迭代写法与踩坑提示写滚动数组版本时有个细节特别容易错如果只用一维数组maxRow[j]里既存当前行的值也存上一行的值。在从左到右遍历时maxRow[j-1]已经是当前行的值而maxRow[j]还没被覆盖仍是上一行的值。所以更新maxRow[j]必须依赖“上一个maxRow[j]上一行”和“maxRow[j-1]当前行左边”并且要在更新j之前把j-1算好。这个操作天然满足因为我们就是从j1往右遍历的。但如果你是先更新maxRow[j]再更新minRow[j]或者反过来就会出问题。因为maxRow[j]的更新依赖minRow的旧值吗依赖它需要minRow[i-1][j]的旧值——但注意minRow[j]此刻还没被覆盖仍然是上一行的值所以直接用没问题可是如果你在更新maxRow[j]之前不小心动过minRow[j]那就张冠李戴了。所以我习惯把两个数组分开更新先算newMax和newMin两个临时变量再统一赋给数组避免交叉污染。具体实现如下public int maxProductPathOptimized(int[][] grid) { int m grid.length; int n grid[0].length; long[] dpMax new long[n]; long[] dpMin new long[n]; // 第一行初始化 dpMax[0] grid[0][0]; dpMin[0] grid[0][0]; for (int j 1; j n; j) { dpMax[j] dpMax[j-1] * grid[0][j]; dpMin[j] dpMin[j-1] * grid[0][j]; } for (int i 1; i m; i) { // 每行第一个元素单独处理只能来自上方 dpMax[0] * grid[i][0]; dpMin[0] * grid[i][0]; for (int j 1; j n; j) { // 候选值来自上方和左侧 long upMax dpMax[j]; // 上一行同列尚未被当前行覆盖 long upMin dpMin[j]; long leftMax dpMax[j-1]; // 当前行左侧已被覆盖 long leftMin dpMin[j-1]; long val grid[i][j]; long curMax Math.max(Math.max(upMax * val, upMin * val), Math.max(leftMax * val, leftMin * val)); long curMin Math.min(Math.min(upMax * val, upMin * val), Math.min(leftMax * val, leftMin * val)); dpMax[j] curMax; dpMin[j] curMin; } } return dpMax[n-1] 0 ? (int) dpMax[n-1] : -1; }这段代码我在本地测试和 LeetCode 上跑过和二维版本结果完全一致。它的空间复杂度从O(m*n)降到了O(n)也就是在最坏情况下只需要两个长度为 n 的 long 数组。如果你愿意继续压甚至可以再把dpMin和dpMax合成一个二维数组dp[2][n]但语义上不如拆开清晰我推荐保持两个一维数组可读性更好。4.3 一行数组到底怎么理解“同时持有两行信息”有同学会对滚动数组的运行过程感到抽象我打个比方想象你在一个传送带上你站在第i行手里握着两个储物柜每个柜子有n个抽屉。传送带把你往前推你看到的柜子里的每个抽屉实际上存的是上一行走到这个格子时的最大值和最小值。你一边走一边把当前格子算好的新值覆盖进抽屉里。等这一行走完你手里的抽屉全变成了当前行的值于是下一轮继续用它们作为“上一行”。整个过程一气呵成不需要把整张表搬来搬去。5. 记忆化搜索实现递归视角下的状态依赖5.1 定义dfs(i,j)返回什么如果你想换个角度理解这道题可以从记忆化搜索入手。我们定义solve(i,j)表示从(0,0)到(i,j)所能得到的最大乘积和最小乘积。为了省事可以定义一个long[][][] memo其中memo[i][j][0]存最大memo[i][j][1]存最小。递归时先查表如果算过就直接返回否则根据(i-1,j)和(i,j-1)的结果依次推导。值得一提的是记忆化搜索的递归方向是从终点往起点回溯但状态转移方程和递推完全一致。写代码时特别注意递归前要先处理边界i0 j0、i0、j0这三条路的转移公式各不相同。我一开始写时忘了拆分这些情况结果数组越界提醒救了命——Java 的ArrayIndexOutOfBoundsException在这种情况下反而是友善的至少能让你快速定位错误而不是给你一个错误的正确答案。5.2 记忆化搜索的性能测试与适用场景我在本地对15 x 15随机矩阵实测记忆化搜索和递推在时间上差距不大大概在几毫秒到十几毫秒之间。递归调用带来的额外开销在这种小规模数据下可以忽略不计。但如果你把矩阵扩大到1000 x 1000递归版本的时间可能会翻两三倍而且递归深度达到 1000 层时某些语言默认栈空间不足会有栈溢出风险。因此我个人的代码习惯是**除非题目明显适合递归建模比如二叉树、区间DP否则矩阵路径类问题优先写递推。**记忆化搜索更适合用来验证递推状态转移方程的正确性相当于拿另一套逻辑“对拍”。6. 易错点、边界用例与实战复盘6.1 负数边界为什么 test case 需要覆盖全负矩阵我在实际刷题和给朋友讲这道题时最常被问到的不是主逻辑而是各种边界用例。这里整理一个我反复验证过的测试矩阵大家可以拿去检验自己的实现输入 grid [[1, -2, 3], [4, -5, 6], [7, -8, 9]] 正确输出1512 路径1 - 4 - 7 - -8 - 9 1*4*7*(-8)*9 -2016 不对 实际最优路径1 - -2 - 3 - 6 - 9 1*(-2)*3*6*9 -324 也不对 再试 1 - 4 - -5 - 6 - 9 1*4*(-5)*6*9 -1080 也不对 最后发现 1 - -2 - -5 - 6 - 9 1*(-2)*(-5)*6*9 540 也不行 最终正确答案是 1 - 4 - 7 - -8 - -5 - 6 - 9 1*4*7*(-8)*(-5)*6*9 60480 等等这不是只能向右或向下吗上面这个例子不行因为路径限制只能向右或向下不能绕回去。我再构造一个更贴合规则的情况一个 2x3 矩阵包含两个负数的“对折路径”。grid [[1, -3, 2], [3, -4, 5]]从(0,0) - (0,1) - (1,1) - (1,2)这条路径乘积是1 * (-3) * (-4) * 5 60。这个用例可以很好地检验dpMin是否真正参与到了最大值的推导里——因为如果没有dpMin[1][1] -3 * -4 12你可能会觉得走到(0,1)时的最小值-3没用但实际上必须靠它乘上-4才能得到12。6.2 全零矩阵和单元素矩阵全零矩阵比较简单任何路径乘积都是 0答案是 0。单元素矩阵也简单如果那个数是负数就返回-1否则返回它本身。这两个用例很多人不屑于测但他们恰恰能暴露初始化逻辑的问题——如果第一行第一列没有正确赋值单元素矩阵直接返回错误结果。6.3 溢出问题为什么返回答案前需要取模但中间不能取模LeetCode 原题要求最终答案对1_000_000_007取模。但注意中间状态不能取模。因为我们要比较的是真实乘积的大小取模后大小关系被破坏了可能让一个真实更大的路径在模意义下反而更小导致决策错误。所以必须全程用long保存完整乘积最后输出答案时再% MOD。这里又是一个典型的“算法正确性优先于数值溢出处理”的案例。6.4 另一个典型坑Java 的Math.max嵌套与可读性当四个候选值摆在一起时很多同学喜欢一行写出四层Math.max嵌套。这在语法上没问题但可读性很差而且容易漏括号编译错误排查烦人。我的习惯是像上面代码那样把每个候选值单独存成变量再分组计算。这样做的好处是出问题后能单步调试去看每个候选值是多少而不是面对一坨嵌套表达式无从下手。7. 双状态DP的通用套路从这道题出发举一反三7.1 哪些题目会用到“同时维护最大和最小”的思想做完这道题值得停下来总结一下。双状态DP在 LeetCode 里其实是一个不小的家族。比如「最大乘积子数组」要同时维护到当前位置的最大乘积和最小乘积因为负数子数组可能被后续负数救回来。「股票买卖含冷冻期」虽然没有负数符号问题但需要维护持有/不持有两种状态本质上是“多个并行状态”。「正则表达式匹配」的 DP 表里每个格子存储的也是一个布尔值而不是单纯的数值——其实也是一种状态扩展。关键认知是当状态转移中掺杂乘法和符号变化时单状态描述往往是不完备的。你能想到多少“状态维度”取决于你对问题本身的信息量认识有多深。本题就是“最值状态被负数符号分裂成两个分支”的一个经典案例。7.2 如何快速识别一道题是否需要双状态我总结了几个信号一旦命中就可以警惕操作里出现了乘法并且元素可能为负。存在类似“取最大”但中间可能经过负数导致结果反向的操作。状态转移需要的“历史最优”不再是一个标量就能唯一确定的。面试官追问“为什么不能只用最大值”时你能明确说出负负得正的例子。当然很多场景也不是非黑即白。比如元素可能为零那么整个路径乘积可能直接变成 0此时你需要重新评估“负数最小态”是否仍然有意义。好在零本身不会反转符号所以维护最小态并不冲突。7.3 空间优化能推广到什么程度滚动数组推广到其他 DP 题时一个通用法则是看当前状态依赖哪些“坐标偏移”的状态。如果只依赖上一行和当前行就可以只保留两行如果依赖上一行和左一行可能需要斜线滚动。这题因为转向只有向下和向右所以滚动到一行非常自然。如果题目允许上下左右四方向走那滚动数组就不能直接套因为状态之间的依赖关系会形成环此时得用最短路或拓扑排序的思路。8. 从暴力到最优的完整递进路线8.1 暴力搜索为什么做不了既然最终状态都清楚了我们不妨回头看看暴力搜索的死穴在哪里。如果直接枚举所有路径也就是在15 x 15的矩阵里从左上到右下要走141428步其中向下 14 步、向右 14 步路径总数是组合数C(28, 14)算下来大约是 4000 万条。每条路径要做 29 次乘法总操作量在十亿量级跑起来非常吃力。更关键的是暴力搜索没法利用重叠子问题——不同路径到达同一个格子后后续完全一致却要被重复计算。8.2 重叠子问题如何被 DP 利用所有 DP 题的核心价值就是规避重复计算。本题中无论从哪条路径到达(i,j)之后从(i,j)到终点的所有路径都是相同的子问题。但因为乘积受前面路径影响我们记录了到达(i,j)的最大和最小乘积相当于把前面所有路径压缩成了两个代表性数值。这两个数值足以代表整个到达状态集合——因为后续格子的正负只会和它们做乘法其他中间数值要么被最大/最小覆盖要么在符号反转时被另一个极值覆盖。因此这两个极值就是足够的状态压缩。8.3 我的刷题建议先写二维DP再优化成一维如果你是在准备面试我建议你把这道题刷三遍。第一遍只写二维双表版本重点是理解状态定义和转移逻辑然后跑通所有边界用例。第二遍用滚动数组优化空间同时手动模拟一遍三行三列的矩阵加深对“当前行/上一行”生命周期的理解。第三遍尝试用记忆化搜索用来验证递推版本是否正确也顺便锻炼递归建模能力。三遍下来这道题就不再是一道题而是一套“DP 完整思考链路”的缩影。9. 这次实际解题中的耗时数据与工具建议刷题时我用 Java 写了个测试脚手架外层循环随机生成 50 组15 x 15矩阵值域从-10000到10000分别跑二维、一维和记忆化搜索三个版本。结果大致如下版本50组平均耗时空间二维双表递推3.2 msO(m*n)一维滚动数组递推2.8 msO(n)记忆化搜索5.1 msO(m*n) 递归栈数据很直观一维滚动数组在当前题目的数据规模下并不占优势因为它省掉的空间在这道题里本来就不多反而可能因为 bit 操作和赋值逻辑略微增加时间开销。但如果矩阵规模放大到1000 x 1000一维版本的优势就会非常明显空间从8 * 10^6字节降到8 * 10^3字节在内存受限的环境里可能是决定成败的因素。我的工具链建议是在本地用JShell跑 LeetCode 题不如直接开 IDE比如 IntelliJ建一个 Java 工程专门写一个Main类把测试矩阵和暴力对拍函数都写在里面。这样每次改完算法可以跑一遍对拍来确认没有回归。对拍函数就用暴力 DFS 枚举所有路径在15 x 15下能跑完虽然慢但能当金标准。这也是我推荐给所有刷算法题朋友的通用工作流。10. 几个关于“为什么这么写”更深的个人体会最后聊聊我自己的体会。很多初学者刷 DP 题时会陷入一个误区背状态转移方程。但如果你不理解dpMin为什么存在、为什么滚动数组要“从后往前”或“从左往右”你就永远只能解决做过的题。LeetCode 1594 这道题的魅力在于它把“负负得正”这样一个初中数学常识巧妙地嵌入了状态设计和转移逻辑里。你不是在背公式而是在翻译现实世界的符号规则。我帮别人 review 代码时见过太多次只维护dpMax导致错误的实现。他们通常是看了两三篇题解把“同时维护最大值和最小值”这句话记住了却不知道为什么于是遇到变体就不知道怎么处理。所以我在这篇文章里花大篇幅解释了双状态的来源。如果你认真读到这里以后遇到“最大乘积子数组”“最大乘积路径”这类题目应该能条件反射地想到先把符号反转这个点想清楚再决定要不要两个极值。还有一个小建议刷题时不要只满足于通过。你可以试着修改题目条件比如“路径方向允许一次向左或向上”思考状态转移会怎么变化滚动数组还能不能用记忆化搜索的 memo 表维度会不会增加。这些“加练”才是真正拉开差距的地方。在我看来算法学习不是比拼刷题数量而是比拼对每一个小决策背后逻辑的挖掘深度。这道 1594你挖得越深收获越大。