本文共 3426 字，大约阅读时间需要 11 分钟。
1. 问题描述：
给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中向右或向下移动。
在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。 返回最大非负积对10 ^ 9 + 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 <= rows, cols <= 15-4 <= grid[i][j] <= 4来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-non-negative-product-in-a-matrix2. 思路分析：
① 因为求解的是二维矩阵中的关于路径的问题，所以一开始想到的是递归的思路去解决，尝试搜索二维矩阵中的所有路径并且在递归方法中传入一个int类型变量来记录这些路径的最大值，当递归的位置到grid[row][col]的时候那么更新历史上路径最大值，但是使用python提交上去超时了
② 除了使用递归尝试所有的路径的乘积的方法之外，还可以使用动态规划的思路去解决，并且使用动态规划的思路也比较容易想到，我们使用两个二维列表来记录到达当前位置的最大值与最小值，这样每次到达当前位置的时候可以使用dp列表的左边与上边的位置对应的值乘以当前grid列表对应的值，这样就求解出到达当前位置的最小值与最大值了，为什么要记录当前位置的最小值呢：因为二维矩阵中是存在负数的情况的，当前面一条路径的乘积为负数的时候而且到达当前grid列表的位置对应的也为负数的时候那么这个时候这条路径的乘积是正数，所以这就构成了到达当前位置的正数乘积了，最后我们需要判断到达grid列表的最后一个位置的时候乘积是正数还是负数来决定返回值的情况
③ 这道题目与之前：乘积最大子数组的是类似的
3. 代码如下：
动态规划代码：
from typing import Listclass Solution: def maxProductPath(self, grid: List[List[int]]) -> int: # 其实这道题目使用动态规划是最简单的依次计算能够到达当前位置的最大选择 r, c = len(grid), len(grid[0]) # 初始化二维列表dp dp1 = [[0] * c for i in range(r)] dp2 = [[0] * c for i in range(r)] # 初始化第一列 dp1[0][0] = dp2[0][0] = grid[0][0] for i in range(1, r): dp1[i][0] = dp1[i - 1][0] * grid[i][0] dp2[i][0] = dp2[i - 1][0] * grid[i][0] # 初始化第一行 for i in range(1, c): dp1[0][i] = dp1[0][i - 1] * grid[0][i] dp2[0][i] = dp2[0][i - 1] * grid[0][i] for i in range(1, r): for j in range(1, c): 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]) 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]) return dp1[r - 1][c - 1] % (10 ** 9 + 7) if dp1[r - 1][c - 1] >= 0 else -1
超时的递归代码：
import sysfrom typing import Listclass Solution: res = -sys.maxsize def dfs(self, grid: List[List[int]], x: int, y: int, r: int, c: int, pos: List[List[int]], mul: int): if x == r and y == c: if self.res < mul: self.res = max(self.res, mul) return # 剪枝假如乘积为0那么不再递归下去 if mul == 0: return for cur in pos: tx = x + cur[0] ty = y + cur[1] if 0 <= tx <= r and 0 <= ty <= c: t = grid[tx][ty] if t != -sys.maxsize: grid[tx][ty] = -sys.maxsize self.dfs(grid, tx, ty, r, c, pos, mul * t) # 回溯 grid[tx][ty] = t def maxProductPath(self, grid: List[List[int]]) -> int: pos = [[1, 0], [0, 1]] t = grid[0][0] grid[0][0] = -sys.maxsize rec = list() rec.append(t) self.dfs(grid, 0, 0, len(grid) - 1, len(grid[0]) - 1, pos, t) for i in grid: if 0 in i and self.res < 0: return 0 return self.res % (10 ** 9 + 7) if self.res >= 0 else -1
转载地址：http://nmgr.baihongyu.com/