C++刷leetcode(1594. 矩阵的最大非负积)【动态规划】
题目描述：给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为负数，则返回 -1 。
注意，取余是在得到最大积之后执行的。
示例 1：
输入：grid = [[-1,-2,-3],
[-2,-3,-3],
[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1
示例 2：
输入：grid = [,
,
]
输出：8
解释：最大非负积对应的路径已经用粗体标出 (1 * 1 * -2 * -4 * 1 = 8)
示例 3：
输入：grid = [,
]
输出：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 <= rows, cols <= 15
-4 <= grid <= 4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-non-negative-product-in-a-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int maxProductPath(vector<vector<int>>& grid) {
//动态规划
//定义
int len1 = grid.size(), len2 = grid.size();
vector<vector<long long> >dp1(len1, vector<long long>(len2, 0));
vector<vector<long long> > dp2(len1, vector<long long>(len2, 0));
//初始化(初始化是有递归公式决定的)
dp1 = grid;
dp2 = grid;
for(int i = 1; i < len1; i++){
dp1 = dp1 * grid;
dp2 = dp2 * grid;
}
for(int i = 1; i < len2; i++){
dp1 = dp1 * grid;
dp2 = dp2 * grid;
}
//递归公式
for(int i = 1; i < len1; i++){
for(int j = 1; j < len2; j++){
dp1=max({dp1*grid, dp1*grid,dp2*grid, dp2*grid});
dp2=min({dp1*grid, dp1*grid,dp2*grid, dp2*grid});
}
}
int mode = 1e9+7;
return dp1 >= 0 ? (int)(dp1 % mode): -1;
}
};
参考链接：https://leetcode-cn.com/problems/maximum-non-negative-product-in-a-matrix/solution/dong-tai-gui-hua-zhu-yi-yu-chu-shi-hua-by-niu-tou-/ {:10_257:}
页:
[1]