1594. 矩阵的最大非负积（Rating 1807）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1594. 矩阵的最大非负积

Rating 1807

思路

对于二维网格从左上走到右下的问题，大概率是动态规划问题。

因为每个格子的状态只与其上面和左面的格子状态有关。

因为负数*负数也可以得到正数，所以我们需要记录路径上乘积最小的负数，以便在后面再遇到负数时有机会得到较大的正数。

因此考虑

对每个格子维护两个值，即最小值和最大值。

代码

MOD = 10 ** 9 + 7

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # dp[0][i][j] 记录经过第(i, j)个格子可以获得的最小值
        # dp[1][i][j] 记录经过第(i, j)个格子可以获得的最大值
        dp = [[[0 for _ in range(n)] for _ in range(m)] for _ in range(2)]
        dp[0][0][0] = grid[0][0] # 初始化第(0, 0)个格子
        dp[1][0][0] = grid[0][0] # 初始化第(0, 0)个格子
        for i in range(1, m): # 遍历所有行，初始化第0列，该列的乘积结果只与上面的乘积结果有关
            dp[0][i][0] = dp[0][i - 1][0] * grid[i][0]
            dp[1][i][0] = dp[0][i][0]
        for i in range(1, n): # 遍历所有列，初始化第0行，该行的乘积结果只与左面的乘积结果有关
            dp[0][0][i] = dp[0][0][i - 1] * grid[0][i]
            dp[1][0][i] = dp[0][0][i]
        for i in range(1, m): # 遍历所有行
            for j in range(1, n): # 遍历所有列
                dp[0][i][j] = min( # 第(i, j)个格子的最小值可能来自
                    dp[0][i - 1][j] * grid[i][j], # 上面格子的最小值 与 当前值相乘
                    dp[1][i - 1][j] * grid[i][j], # 上面格子的最大值 与 当前值相乘
                    dp[0][i][j - 1] * grid[i][j], # 左面格子的最小值 与 当前值相乘
                    dp[1][i][j - 1] * grid[i][j], # 左面格子的最大值 与 当前值相乘
                )
                dp[1][i][j] = max( # 同上
                    dp[0][i - 1][j] * grid[i][j],
                    dp[1][i - 1][j] * grid[i][j],
                    dp[0][i][j - 1] * grid[i][j],
                    dp[1][i][j - 1] * grid[i][j],
                )
        return -1 if dp[1][-1][-1] < 0 else dp[1][-1][-1] % MOD # 按照题目规则返回答案