题目描述

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

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

返回 最大非负积 对 10^9 + 7 取余 的结果。如果最大积为负数，则返回 -1。

注意，取余是在得到最大积之后执行的。

样例

输入：grid = [[-1,-2,-3],
             [-2,-3,-3],
             [-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1

输入：grid = [[1,-2,1],
              [1,-2,1],
              [3,-4,1]]
输出：8
解释：最大非负积对应的路径为 (1 * 1 * -2 * -4 * 1 = 8)

输入：grid = [[1, 3],
              [0,-4]]
输出：0
解释：最大非负积对应的路径为 (1 * 0 * -4 = 0)

输入：grid = [[ 1, 4,4,0],
              [-2, 0,0,1],
              [ 1,-1,1,1]]
输出：2
解释：最大非负积对应的路径为 (1 * -2 * 1 * -1 * 1 * 1 = 2)

限制

• 1 <= rows, cols <= 15
• -4 <= grid[i][j] <= 4

算法

(动态规划) $O(rc)$

1. 由于乘积有负数，且两个负数的乘积就是正数，所以需要两个状态，最大值和最小值。
2. 设状态 $f(i, j)$ 表示从左上角到当前位置的最大值，$g(i, j)$ 表示从左上角到当前位置的最小值。
3. 初始时，$f(0, 0) = g(0, 0) = grid(0, 0)$，其余待定。
4. 转移时
   • 如果 $grid(i, j) == 0$，则 $f(i, j) = g(i, j) = 0$。
   • 如果 $grid(i, j) > 0$，则 $f(i, j) = \max(f(i - 1, j), f(i, j - 1)) * grid(i, j)$，$g(i, j) = \min(g(i - 1, j), g(i, j - 1)) * grid(i, j)$。
   • 如果 $grid(i, j) < 0$，则 $f(i, j) = \min(g(i - 1, j), g(i, j - 1)) * grid(i, j)$，$g(i, j) = \max(f(i - 1, j), f(i, j - 1)) * grid(i, j)$。
5. 最终答案为 $f(r - 1, c - 1)$。

时间复杂度

• 状态数为 $O(rc)$，转移时间为常数，故总时间复杂度为 $O(rc)$。

空间复杂度

• 需要 $O(rc)$ 的额外空间记录状态。

C++ 代码

#define LL long long

class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        const int r = grid.size(), c = grid[0].size();
        const int mod = 1000000007;
        vector<vector<LL>> f(r, vector<LL>(c));
        vector<vector<LL>> g(r, vector<LL>(c));

        f[0][0] = g[0][0] = grid[0][0];
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 0) {
                    f[i][j] = g[i][j] = 0;
                } else if (grid[i][j] > 0) {
                    if (i > 0 && j > 0) {
                        f[i][j] = max(f[i - 1][j], f[i][j - 1]) * grid[i][j];
                        g[i][j] = min(g[i - 1][j], g[i][j - 1]) * grid[i][j];
                    } else if (i > 0) {
                        f[i][j] = f[i - 1][j] * grid[i][j];
                        g[i][j] = g[i - 1][j] * grid[i][j];
                    } else if (j > 0) {
                        f[i][j] = f[i][j - 1] * grid[i][j];
                        g[i][j] = g[i][j - 1] * grid[i][j];
                    }
                } else {
                    if (i > 0 && j > 0) {
                        f[i][j] = min(g[i - 1][j], g[i][j - 1]) * grid[i][j];
                        g[i][j] = max(f[i - 1][j], f[i][j - 1]) * grid[i][j];
                    } else if (i > 0) {
                        f[i][j] = g[i - 1][j] * grid[i][j];
                        g[i][j] = f[i - 1][j] * grid[i][j];
                    } else if (j > 0) {
                        f[i][j] = g[i][j - 1] * grid[i][j];
                        g[i][j] = f[i][j - 1] * grid[i][j];
                    }
                }
            }

        if (f[r - 1][c - 1] < 0)
            f[r - 1][c - 1] = -1;

        return f[r - 1][c - 1] % mod;
    }
};