日期: 2026年3月23日

目标

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 10^9 + 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.length
• n == grid[i].length
• 1 <= m, n <= 15
• -4 <= grid[i][j] <= 4

思路

有一个矩阵 grid，从左上角 (0, 0) 出发向右或向下移动到达 (m - 1, n - 1)。路径的乘积指路径经过的所有元素乘积，返回最大的非负乘积。

由于存在负值，总的最大非负路径可能由最小值与当前值相乘得到。

定义 dp[i][j][0] 表示到达 (i, j) 的最大路径积，dp[i][j][1] 表示到达 (i, j) 的最小路径积。状态转移方程为：

• dp[i][j][0] = Math.max(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]) 最小值与当前值相乘
• dp[i][j][0] = Math.max(dp[i][j][0], Math.max(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j])) 最大值与当前值相乘
• dp[i][j][1] = Math.min(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]) 最小值与当前值相乘
• dp[i][j][1] = Math.min(dp[i][j][1], Math.min(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j])) 最大值与当前值相乘

代码

/**
 * @date 2026-03-23 9:12
 */
public class MaxProductPath1594 {

    public int maxProductPath(int[][] grid) {
        int mod = 1000000007;
        int m = grid.length;
        int n = grid[0].length;
        long[][][] dp = new long[m][n][2];
        dp[0][0][0] = grid[0][0];
        dp[0][0][1] = grid[0][0];
        for (int j = 1; j < n; j++) {
            dp[0][j][0] = dp[0][j - 1][0] * grid[0][j];
            dp[0][j][1] = dp[0][j - 1][1] * grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            dp[i][0][0] = dp[i - 1][0][0] * grid[i][0];
            dp[i][0][1] = dp[i - 1][0][1] * grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
                dp[i][j][0] = Math.max(dp[i][j][0], Math.max(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j]));
                dp[i][j][1] = Math.min(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
                dp[i][j][1] = Math.min(dp[i][j][1], Math.min(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j]));
            }
        }
        return dp[m - 1][n - 1][0] < 0 ? -1 : (int) (dp[m - 1][n - 1][0] % mod);
    }

}

性能