题目描述

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

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

返回 最大非负积 对 $10e9+ 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)

示例 4：
输入：grid = [[ 1, 4,4,0],
             [-2, 0,0,1],
             [ 1,-1,1,1]]
输出：2
解释：最大非负积对应的路径已经用粗体标出 (1 * -2 * 1 * -1 * 1 * 1 = 2)

算法1

(动态规划) $O(n^2)$

Leetcode 64. 最小路径和 和 Leetcode152. 乘积最大子数组 合体题。

状态表示：
$f[i][j]$表示从$(0, 0)$到$(i, j)$路径上的${最大积，最小积}$

状态转移：
只能向下或者向右走，所以$f[i][j]$会从$f[i][j - 1]$和$f[i - 1][j]$转移过来；
转移时要分类考虑当前格子的数是不是负数，因为负数乘以最小积可能得到更大的数，负数乘以最大积可能得到更小的数。

时间复杂度

一共$O(n^2)$个状态，每次状态转移是$O(1)$，所以总时间复杂度$O(n^2)$

参考文献

C++ 代码

typedef pair<long long, long long> PLL;
const int MOD = 1e9 + 7;

class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<PLL>> f(m, vector<PLL>(n));

        // 初始化(0, 0)
        f[0][0].first = grid[0][0], f[0][0].second = grid[0][0];
        // 初始化第一行
        for (int j = 1; j < n; ++j){
            PLL pre = f[0][j - 1];
            long long max_prod = pre.first, min_prod = pre.second, num = grid[0][j];
            if (num < 0)
                f[0][j] = {num * min_prod, num * max_prod};
            else 
                f[0][j] = {num * max_prod, num * min_prod};
        }

        // 初始化第一列
        for (int i = 1; i < m; ++i){
            PLL pre = f[i - 1][0];
            long long max_prod = pre.first, min_prod = pre.second, num = grid[i][0];
            if (num < 0)
                f[i][0] = {num * min_prod, num * max_prod};
            else 
                f[i][0] = {num * max_prod, num * min_prod};
        }

        // 状态转移
        for (int i = 1; i < m; ++i){
            for (int j = 1; j < n; ++j){
                long long num = grid[i][j];
                PLL pre1 = f[i - 1][j], pre2 = f[i][j - 1];
                long long max_prod1 = pre1.first, min_prod1 = pre1.second, max_prod2 = pre2.first, min_prod2 = pre2.second;
                if (num < 0){
                    f[i][j] = {max(min_prod1 * num, min_prod2 * num), min(max_prod1 * num, max_prod2 * num)};
                }
                else{
                    f[i][j] = {max(max_prod1 * num, max_prod2 * num), min(min_prod1 * num, min_prod2 * num)};
                }
            }
        }

        int res = (f[m - 1][n - 1].first) % MOD;
        // 达不到0的给-1
        return res >= 0 ? res : -1;
    }
};