题目
给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。
**注意，**取余是在得到最大积之后执行的。
示例 1：
输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]] 输出：-1 解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。
示例 2：
输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]] 输出：8 解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)
示例 3：
输入：grid = [[1,3],[0,-4]] 输出：0 解释：最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 15-4 <= grid[i][j] <= 4
解题思路
在每一个格子 $(i, j)$，由于我们不知道后面会不会遇到负数，所以我们需要同时记录到达这里的两个极端：
最大乘积 ($dp_{max}[i, j]$)：记录从起点到当前位置能得到的最大乘积。
最小乘积 ($dp_{min}[i, j]$)：记录从起点到当前位置能得到的最小乘积（尤其是绝对值很大的负数）。
由于只能向右或向下移动，到达 $(i, j)$ 的路径只能来自上方 $(i-1, j)$ 或左方 $(i, j-1)$。
当你到达格子 grid[i][j] 时，设当前值为 $v$：
如果 $v > 0$：
最大积来自“之前的最大积 $\times v$”。
最小积来自“之前的最小积 $\times v$”。
如果 $v < 0$：
最大积来自“之前的最小积 $\times v$”（负负得正，翻身做主人）。
最小积来自“之前的最大积 $\times v$”（正负得负，变得更小）。
如果 $v = 0$：
- 最大积和最小积都是 $0$。
数学表达：
$$dp_{max}[i][j] = \max(dp_{max}[i-1][j], dp_{max}[i][j-1]) \cdot v \quad (\text{若 } v \ge 0)$$
$$dp_{max}[i][j] = \min(dp_{min}[i-1][j], dp_{min}[i][j-1]) \cdot v \quad (\text{若 } v < 0)$$
需要注意的：
数据溢出：虽然矩阵只有 $15 \times 15$，且每个数最大只有 $4$，但路径长度最长是 $15+15-1 = 29$。最大乘积约为 $4^{29} = 2^{58}$。这个数值超过了
int32（最大约 $2 \cdot 10^9$），但能装进int64。所以请务必使用long long(C++) 或int64(Go/Rust)。先计算，后取余：题目要求先找最大积，最后再对 $10^9 + 7$ 取余。千万不要在中间过程中取余，否则会破坏负号和大小比较的逻辑（取模运算会丢失大小关系）。
边界初始化：
起点 $(0,0)$ 的 $dp_{max}$ 和 $dp_{min}$ 都是
grid[0][0]。第一行只能从左边来，第一列只能从上面来，需要单独处理循环。
算法复杂度
时间复杂度：$O(m \times n)$，我们需要遍历整个矩阵一次。
空间复杂度：$O(m \times n)$，用于存储两个 DP 矩阵（当然，如果你想进阶一下，可以用滚动数组优化到 $O(n)$）。
具体代码
func maxProductPath(grid [][]int) int {
m := len(grid[0])
n := len(grid)
mod := int64(1e9 + 7)
dp_max := make([][]int64, n)
dp_min := make([][]int64, n)
for i := range n {
dp_max[i] = make([]int64, m)
dp_min[i] = make([]int64, m)
}
dp_max[0][0] = int64(grid[0][0])
dp_min[0][0] = int64(grid[0][0])
// 第一行和列
for i := 1; i < max(m, n); i++ {
if i < m {
dp_max[0][i] = dp_max[0][i - 1] * int64(grid[0][i])
dp_min[0][i] = dp_max[0][i]
}
if i < n {
dp_max[i][0] = dp_max[i - 1][0] * int64(grid[i][0])
dp_min[i][0] = dp_max[i][0]
}
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
val := int64(grid[i][j])
if val > 0 {
dp_max[i][j] = max(dp_max[i - 1][j] * val, dp_max[i][j - 1] * val)
dp_min[i][j] = min(dp_min[i - 1][j] * val, dp_min[i][j - 1] * val)
} else {
dp_max[i][j] = max(dp_min[i - 1][j] * val, dp_min[i][j - 1] * val)
dp_min[i][j] = min(dp_max[i - 1][j] * val, dp_max[i][j - 1] * val)
}
}
}
if dp_max[n - 1][m - 1] < 0 {
return -1
}
return int(dp_max[n - 1][m - 1] % mod)
}
use std::cmp;
impl Solution {
pub fn max_product_path(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mod_val: i64 = 1_000_000_007;
// 1. 初始化 DP 数组：Rust 可以一行搞定二维向量的初始化
// vec![初始值; 长度]
let mut dp_max = vec![vec![0i64; m]; n];
let mut dp_min = vec![vec![0i64; m]; n];
// 2. 起点初始化
dp_max[0][0] = grid[0][0] as i64;
dp_min[0][0] = grid[0][0] as i64;
// 3. 初始化第一行和第一列
// 使用 std::cmp::max(m, n) 保持你之前的逻辑
for i in 1..cmp::max(m, n) {
if i < m {
dp_max[0][i] = dp_max[0][i - 1] * grid[0][i] as i64;
dp_min[0][i] = dp_max[0][i];
}
if i < n {
dp_max[i][0] = dp_max[i - 1][0] * grid[i][0] as i64;
dp_min[i][0] = dp_max[i][0];
}
}
// 4. 动态规划填充
for i in 1..n {
for j in 1..m {
let val = grid[i][j] as i64;
if val >= 0 {
// Rust 中比较两个数可以用 a.max(b)
dp_max[i][j] = cmp::max(dp_max[i - 1][j], dp_max[i][j - 1]) * val;
dp_min[i][j] = cmp::min(dp_min[i - 1][j], dp_min[i][j - 1]) * val;
} else {
// 负数：最大变最小，最小变最大
dp_max[i][j] = cmp::min(dp_min[i - 1][j], dp_min[i][j - 1]) * val;
dp_min[i][j] = cmp::max(dp_max[i - 1][j], dp_max[i][j - 1]) * val;
}
}
}
// 5. 结果处理
let res = dp_max[n - 1][m - 1];
if res < 0 {
-1
} else {
(res % mod_val) as i32
}
}
}