1594. 矩阵的最大非负积

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

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

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

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

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 15
-4 <= grid[i][j] <= 4

思路

首先，这是一个典型的dp问题，要求从左上角到右下角的路径乘积和最大非负积取余的结果。

可以使用两个和gird大小一致的数组big,sml分别存放到某个位置（i,j）的最大和最小乘积。

计算时注意，最上一行没有来自上的计算，最左一行没有来自左的计算，所以计算时先初始化（0，0）位置的big[0][0]=sml[0][0]=grid[0][0],然后计算最上一行、最左一行，最后计算剩下的。

点击展开/折叠

class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        const int MOD = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        
        vector<vector<long long>> big(m, vector<long long>(n));
        vector<vector<long long>> sml(m, vector<long long>(n));
        
        big[0][0] = grid[0][0];
        sml[0][0] = grid[0][0];
        
        for (int i = 1; i < m; ++i) {
            big[i][0] = sml[i][0] = (long long)big[i-1][0] * grid[i][0];
        }
        
        for (int j = 1; j < n; ++j) {
            big[0][j] = sml[0][j] = (long long)big[0][j-1] * grid[0][j];
        }
        
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                vector<long long> candidates = {
                    (long long)big[i-1][j] * grid[i][j],
                    (long long)sml[i-1][j] * grid[i][j],
                    (long long)big[i][j-1] * grid[i][j],
                    (long long)sml[i][j-1] * grid[i][j]
                };
                big[i][j] = *max_element(candidates.begin(), candidates.end());
                sml[i][j] = *min_element(candidates.begin(), candidates.end());
            }
        }
        
        return big[m-1][n-1] >= 0 ? (big[m-1][n-1] % MOD) : -1;
    }
};

相关文章

1594. 矩阵的最大非负积

思路

CATALOG