1594. 矩阵的最大非负积

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • 状态机DP
  • 网格图DP
  • 数学

思路

一、问题概述

给定一个大小为 \(m \times n\) 的整数矩阵 grid，从左上角 \((1,1)\) 出发，只能向右或向下移动，最终到达右下角 \((m,n)\)。 路径的乘积定义为沿途所有格子数值的乘积。

目标是：

  • 在所有合法路径中，求最大的非负乘积；
  • 若所有路径的乘积均为负数，则返回 \(-1\)；
  • 否则返回结果对 \(10^9+7\) 取模后的值。

二、动态规划建模的核心难点

与普通路径 DP 不同，本题的关键困难在于：

  • 矩阵中存在负数
  • 乘积在遇到负数时会发生“符号翻转”
  • “当前最大值”并不能保证后续仍然最优

因此，单一状态无法刻画完整信息。

三、状态定义

为了解决负数带来的不确定性，引入双状态 DP： \[ \begin{aligned} mx[i][j] &: \text{从 } (1,1) \text{ 到 } (i,j) \text{ 的所有路径中，乘积的最大值} \\ mi[i][j] &: \text{从 } (1,1) \text{ 到 } (i,j) \text{ 的所有路径中，乘积的最小值} \end{aligned} \] 解释：

  • mx 用于捕捉“当前看起来最优”的路径；
  • mi 用于在未来遇到负数时，通过“负负得正”反转为最大值。

四、动态规划的初始值（Initialization）

1. 起点

\[ mx[1][1] = mi[1][1] = grid[1][1] \]

起点只有一条路径，最大值和最小值均为自身。

2. 第一列（只能从上往下）

对于 \(i = 2 \sim m\)： \[ mx[i][1] = mi[i][1] = \prod_{k=1}^{i} grid[k][1] \] 因为路径唯一，不存在选择问题。

3. 第一行（只能从左往右）

对于 \(j = 2 \sim n\)： \[ mx[1][j] = mi[1][j] = \prod_{k=1}^{j} grid[1][k] \] 同理，路径唯一。

五、状态转移方程（Transition）

设当前格子的值为： \[ x = grid[i][j] \] 状态仅可能来自两个前驱：\((i-1,j)\) 或 \((i,j-1)\)。

情况一：当前值为非负数（\(x \ge 0\)）

乘以非负数时，大小关系不发生翻转： \[ \begin{aligned} mx[i][j] &= \max\left(mx[i-1][j],\ mx[i][j-1]\right) \cdot x \\ mi[i][j] &= \min\left(mi[i-1][j],\ mi[i][j-1]\right) \cdot x \end{aligned} \]

情况二：当前值为负数（\(x < 0\)）

乘以负数时，最大值与最小值的角色互换： \[ \begin{aligned} mx[i][j] &= \min\left(mi[i-1][j],\ mi[i][j-1]\right) \cdot x \\ mi[i][j] &= \max\left(mx[i-1][j],\ mx[i][j-1]\right) \cdot x \end{aligned} \] 这是本题最核心、也最容易写错的地方。

六、结果的判定（Answer）

最终目标位置为 \((m,n)\)。

  • 若 \[ mx[m][n] < 0 \] 说明不存在非负积路径，返回 \(-1\)。

  • 否则，返回 \[ mx[m][n] \bmod (10^9 + 7) \]

七、为什么 中途绝对不能取模

这是本题一个非常关键的工程与数学细节。

1. 动态规划中需要进行“真实大小比较”

在状态转移中，存在如下操作：

  • max(...)
  • min(...)
  • 判断正负号（是否 < 0）

这些操作依赖真实数值大小与符号。

2. 取模会破坏真实数值关系

模运算满足： \[ a \equiv b \pmod{MOD} \] 但并不保证：

  • \(a\) 与 \(b\) 的大小关系相同
  • \(a\) 与 \(b\) 的正负号相同

例如： \[ -2 \bmod (10^9+7) = 1000000005 \]

  • 真实值是 负数
  • 取模后却变成了一个巨大的正数

这会直接导致：

  • min / max 判断错误
  • 正负翻转逻辑彻底失效
  • 动态规划状态被污染，后续结果全部错误

3. 正确策略

在整个 DP 过程中，必须保存“真实乘积值”； 只有在最终答案输出时，才允许取模。

这也是为什么代码中：

  • mx、mi 使用 long long
  • 模运算只出现在 return 语句

八、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    static const int mod = 1e9 + 7;
    int maxProductPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        long long mx[20][20], mi[20][20], mul = grid[0][0];
        mx[1][1] = mi[1][1] = mul;
        for (int i = 2; i <= m; ++i)
            mul *= grid[i - 1][0], mx[i][1] = mi[i][1] = mul;
        mul = grid[0][0];
        for (int j = 2; j <= n; ++j)
            mul *= grid[0][j - 1], mx[1][j] = mi[1][j] = mul;
        for (int i = 2; i <= m; ++i) {
            for (int j = 2; j <= n; ++j) {
                long long x = grid[i - 1][j - 1];
                mx[i][j] = grid[i - 1][j - 1] < 0
                               ? min(mi[i - 1][j], mi[i][j - 1]) * x
                               : max(mx[i - 1][j], mx[i][j - 1]) * x;
                mi[i][j] = grid[i - 1][j - 1] < 0
                               ? max(mx[i - 1][j], mx[i][j - 1]) * x
                               : min(mi[i - 1][j], mi[i][j - 1]) * x;
            }
        }
        return mx[m][n] < 0 ? -1 : mx[m][n] % mod;
    }
};