本文主要是介绍【网格dp】力扣1594. 矩阵的最大非负积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给你一个大小为 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)
动态规划
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>> maxgt(m, vector<long long>(n));vector<vector<long long>> mingt(m, vector<long long>(n));maxgt[0][0] = mingt[0][0] = grid[0][0];for(int i = 1; i < n; i++){maxgt[0][i] = mingt[0][i] = maxgt[0][i-1] * grid[0][i] ;}for(int i = 1; i < m;i++){maxgt[i][0] = mingt[i][0] = maxgt[i-1][0] * grid[i][0] ;}for(int i = 1;i < m; i++){for(int j = 1; j < n; j++){if(grid[i][j] >= 0){maxgt[i][j] = max(maxgt[i-1][j],maxgt[i][j-1]) * grid[i][j];mingt[i][j] = min(mingt[i-1][j],mingt[i][j-1]) * grid[i][j];}else{maxgt[i][j] = min(mingt[i-1][j],mingt[i][j-1]) * grid[i][j];mingt[i][j] = max(maxgt[i-1][j],maxgt[i][j-1]) * grid[i][j];}}}if(maxgt[m-1][n-1] < 0){return -1;}else{return maxgt[m-1][n-1] % MOD;}}
};
这道题要计算乘法的积，由于表格中可能出现负数，所以我们要维护两个数组，一个用来储存最小值，一个用来储存最大值。然后对grid进行遍历的同时记录这个网格的最小路径和最大路径，当grid为正数的时候，则与最大值相乘可以得到最大值，与最小值相乘得到最小值。当grid为负数的时候，则与最小值相乘得到最大值，与最大值相乘得到最小值。
最后一格如果最大值是负数，则返回-1，否则返回最大值。
这篇关于【网格dp】力扣1594. 矩阵的最大非负积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
