C++刷leetcode(1594. 矩阵的最大非负积)【动态规划】

糖逗

题目描述：

1. 给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
   
2. 
   
3. 在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
   
4. 
   
5. 返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为负数，则返回 -1 。
   
6. 
   
7. 注意，取余是在得到最大积之后执行的。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入：grid = [[-1,-2,-3],
    
14.              [-2,-3,-3],
    
15.              [-3,-3,-2]]
    
16. 输出：-1
    
17. 解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1
    
18. 示例 2：
    
19. 
    
20. 输入：grid = [[1,-2,1],
    
21.              [1,-2,1],
    
22.              [3,-4,1]]
    
23. 输出：8
    
24. 解释：最大非负积对应的路径已经用粗体标出 (1 * 1 * -2 * -4 * 1 = 8)
    
25. 示例 3：
    
26. 
    
27. 输入：grid = [[1, 3],
    
28.              [0,-4]]
    
29. 输出：0
    
30. 解释：最大非负积对应的路径已经用粗体标出 (1 * 0 * -4 = 0)
    
31. 示例 4：
    
32. 
    
33. 输入：grid = [[ 1, 4,4,0],
    
34.              [-2, 0,0,1],
    
35.              [ 1,-1,1,1]]
    
36. 输出：2
    
37. 解释：最大非负积对应的路径已经用粗体标出 (1 * -2 * 1 * -1 * 1 * 1 = 2)
    
38.  
    
39. 
    
40. 提示：
    
41. 
    
42. 1 <= rows, cols <= 15
    
43. -4 <= grid[i][j] <= 4
    
44. 
    
45. 来源：力扣（LeetCode）
    
46. 链接：https://leetcode-cn.com/problems/maximum-non-negative-product-in-a-matrix
    
47. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int maxProductPath(vector<vector<int>>& grid) {
   
4.         //动态规划
   
5.         //定义
   
6.         int len1 = grid.size(), len2 = grid[0].size();
   
7.         vector<vector<long long> >dp1(len1, vector<long long>(len2, 0));
   
8.         vector<vector<long long> > dp2(len1, vector<long long>(len2, 0));
   
9.         //初始化(初始化是有递归公式决定的)
   
10.         dp1[0][0] = grid[0][0];
    
11.         dp2[0][0] = grid[0][0];
    
12.         for(int i = 1; i < len1; i++){
    
13.             dp1[i][0] = dp1[i-1][0] * grid[i][0];
    
14.             dp2[i][0] = dp2[i-1][0] * grid[i][0];
    
15.         }
    
16.         for(int i = 1; i < len2; i++){
    
17.             dp1[0][i] = dp1[0][i-1] * grid[0][i];
    
18.             dp2[0][i] = dp2[0][i-1] * grid[0][i];
    
19.         }
    
20.         //递归公式
    
21.         for(int i = 1; i < len1; i++){
    
22.             for(int j = 1; j < len2; j++){
    
23.                 dp1[i][j]=max({dp1[i-1][j]*grid[i][j], dp1[i][j-1]*grid[i][j],dp2[i-1][j]*grid[i][j], dp2[i][j-1]*grid[i][j]});
    
24.                 dp2[i][j]=min({dp1[i-1][j]*grid[i][j], dp1[i][j-1]*grid[i][j],dp2[i-1][j]*grid[i][j], dp2[i][j-1]*grid[i][j]});
    
25.             }
    
26.         }
    
27.         int mode = 1e9+7;
    
28.         return dp1[len1-1][len2-1] >= 0 ? (int)(dp1[len1-1][len2-1] % mode)  : -1;
    
29. 
    
30.     }
    
31. };

复制代码

参考链接：https://leetcode-cn.com/problems ... hi-hua-by-niu-tou-/

糖逗