1. 问题背景与核心挑战

LeetCode 1594题要求我们在一个充满正负数的矩阵中，从左上角到右下角寻找一条路径，使得路径上所有数字的乘积是最大的非负数。这个问题看似简单，实则暗藏玄机——负数乘以负数会变成正数，这意味着我们不能简单地记录当前路径的最大乘积，还需要跟踪最小乘积。

我第一次遇到这个问题时，直觉告诉我要用动态规划，但具体怎么设计状态转移方程却让我思考了很久。后来通过几个测试案例的模拟，才明白需要同时维护最大和最小两个状态数组。这种"双状态"的设计模式，在很多涉及正负交替最优解的问题中都会出现。

2. 动态规划解法设计

2.1 状态定义与初始化

我们定义两个m×n的二维数组：

• max_dp[i][j] 表示到达(i,j)位置时的最大乘积
• min_dp[i][j] 表示到达(i,j)位置时的最小乘积

初始化时，max_dp[0][0]和min_dp[0][0]都设为grid[0][0]。边界条件处理需要特别注意：

# 初始化第一列 for i in range(1, m): max_dp[i][0] = max_dp[i-1][0] * grid[i][0] min_dp[i][0] = min_dp[i-1][0] * grid[i][0] # 初始化第一行 for j in range(1, n): max_dp[0][j] = max_dp[0][j-1] * grid[0][j] min_dp[0][j] = min_dp[0][j-1] * grid[0][j]

2.2 状态转移方程

对于每个非边界的网格(i,j)，我们需要考虑从上或从左转移过来的四种可能性：

1. 上方的max_dp × 当前值
2. 上方的min_dp × 当前值
3. 左侧的max_dp × 当前值
4. 左侧的min_dp × 当前值

然后取这四种情况的最大值和最小值分别更新max_dp[i][j]和min_dp[i][j]：

for i in range(1, m): for j in range(1, n): candidates = [ max_dp[i-1][j] * grid[i][j], min_dp[i-1][j] * grid[i][j], max_dp[i][j-1] * grid[i][j], min_dp[i][j-1] * grid[i][j] ] max_dp[i][j] = max(candidates) min_dp[i][j] = min(candidates)

3. 实现细节与优化技巧

3.1 空间优化技巧

原始的O(mn)空间复杂度可以优化到O(n)：

def maxProductPath(grid): m, n = len(grid), len(grid[0]) max_dp = [0] * n min_dp = [0] * n # 初始化第一行 max_dp[0] = min_dp[0] = grid[0][0] for j in range(1, n): max_dp[j] = min_dp[j] = max_dp[j-1] * grid[0][j] for i in range(1, m): # 处理每行的第一个元素 old_max = max_dp[0] max_dp[0] = min_dp[0] = max_dp[0] * grid[i][0] for j in range(1, n): candidates = [ old_max * grid[i][j], min_dp[j] * grid[i][j], max_dp[j-1] * grid[i][j], min_dp[j-1] * grid[i][j] ] old_max, max_dp[j] = max_dp[j], max(candidates) min_dp[j] = min(candidates) return max_dp[-1] % (10**9+7) if max_dp[-1] >= 0 else -1

3.2 边界条件处理

几个容易出错的边界情况：

1. 当grid[0][0]为0时，初始乘积就是0
2. 当矩阵只有1个元素时，直接返回该元素
3. 最终结果需要取模10^9+7
4. 如果没有非负乘积，返回-1

4. 复杂度分析与变种问题

4.1 时间复杂度分析

标准的动态规划解法：

• 时间复杂度：O(mn)，因为需要遍历整个矩阵
• 空间复杂度：原始版本O(mn)，优化后O(n)

4.2 相关问题扩展

1. 最小乘积路径：同样的方法，只需关注min_dp的最终值
2. 路径数量统计：可以增加一个count数组记录达到当前极值的路径数
3. 三维矩阵扩展：如果矩阵变成三维，状态转移需要考虑三个方向

5. 常见错误与调试技巧

5.1 典型错误案例

1. 只维护最大值：遇到负数时可能错过最优解

# 错误示例 - 只维护max_dp max_dp[i][j] = max(max_dp[i-1][j], max_dp[i][j-1]) * grid[i][j]

2. 忽略整数溢出：虽然Python不用担心，但在其他语言中需要注意
3. 初始化错误：忘记处理第一行和第一列的特殊情况

5.2 调试建议

1. 打印中间状态：在循环中打印max_dp和min_dp的值
2. 使用小测试案例：比如2x2矩阵，手动计算验证
3. 检查边界：专门测试1x1、1xn、mx1等特殊矩阵

6. 实际应用场景

这种双状态动态规划的思想在以下场景中都有应用：

1. 股票交易问题（考虑持有/不持有状态）
2. 游戏得分计算（最大/最小得分）
3. 物理模拟（能量最大/最小状态）
4. 路径规划（考虑时间/成本的多目标优化）

我在解决一个实际的生产调度问题时，就借鉴了这种思路。需要同时考虑最快完成时间和最低成本两种状态，通过维护两个状态数组，最终找到了最优的平衡方案。