5521. 矩阵的最大非负积 [medium]
5521. 矩阵的最大非负积 [medium]
给你一个大小为 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
Second Try
2020-09-20
赛后重新写的，忽略掉在dp矩阵时候对正负的苛求，完全按照求极大值极小值来写，最后判断是否为正数即可。
毕竟对于maxv和minv而言，遇到grid[i][j]为负数的时候，minv = maxv grid[i][j], maxv = minv grid[i][j]这两个等式并不在乎maxv和minv为正数还是负数。之前还是自己想太多了，严格要求maxv为正数，minv为负数，导致需要填的坑越来越多。
其次对于i<0和j<0的情况，直接进行封堵，只允许从左上角出发，而不允许从边界出发，因此应该直接返回None，边界则直接对dp_min[0][0]和dp_max[0][0]进行初始化设置。
为了避免空字符串和None两者同时引入导致的问题，直接对minv返回正无穷大，对maxv返回负无穷大。如果有一条路可以选，都不会选择到错误的minv和maxv。但如果该位置就是无路可选，那么最后的结果会将其剔除掉。按照现在不考虑dp中正负的情况，不会出现无路可走的情况。
简化之后，思路终于比first try里面考虑严格正负值的情况清晰了许多。本来就应该是一到轻松的套路题，结果浪费了那么多时间填坑，超时了才做出来。
class Solution:
def maxProductPath(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp_min = [[""] * n for _ in range(m)]
dp_max = [[""] * n for _ in range(m)]
dp_min[0][0], dp_max[0][0] = grid[0][0], grid[0][0]
def pp_min_max(i, j, req_min):
if i < 0 or j < 0:
# return None # 不允许通行
if req_min:
# 反其道而行之，不会被选择到，但如果左边和上边过来的都是错误选择呢？
return float('inf')
else:
return float('-inf')
if req_min and dp_min[i][j] != "":
return dp_min[i][j]
if (not req_min) and dp_max[i][j] != "":
return dp_max[i][j]
# 如果都是错误选择，则min_choice为float('inf')，max_choice为负无穷float('-inf'),最后还是会被剔除掉
min_choice = min(pp_min_max(i - 1, j, True), pp_min_max(i, j - 1, True))
max_choice = max(pp_min_max(i - 1, j, False), pp_min_max(i, j - 1, False))
# 这里隐含着dp_min为负数的假设，但计算到最后并不在乎是否真的为负, 最后有判断要求dp_max的maxv>=0即可，这是逻辑上不太确定的地方。
# 其实再看一遍，不管dp_min和dp_max是否为负数，计算dp_max和dp_min遇到grid[i][j]为负数都是下面的逻辑，因此并没有问题。
if grid[i][j] >= 0:
dp_max[i][j] = grid[i][j] * max_choice
dp_min[i][j] = grid[i][j] * min_choice
else:
dp_max[i][j] = grid[i][j] * min_choice
dp_min[i][j] = grid[i][j] * max_choice
return dp_min[i][j] if req_min else dp_max[i][j]
maxv = pp_min_max(m - 1, n - 1, False)
return maxv % (10 ** 9 + 7) if maxv >= 0 else -1
First Try
2020-09-20
看到这题目就觉得是轻车熟路的动态规划问题，每个节点无非是从左边和上边到达当前点，同时再考虑下负数和正数的问题，轻轻松松。
结果不知道是不是因为半个月没做leetcode题目了，写来写去总是有bug。
- 一开始的初始值设置为空字符串，但如果所在位置没有正数或负数，需要找另一个标记，于是用上了None，空字符串和None就混淆到了一起，需要区分判断。
- 对于DP矩阵，也不知道是要设置n * n还是(n + 1) * (n + 1)更方便些，写起来有点别扭。选择n * n矩阵之后，认为i<0或者j<0只要返回1就行了。后来发现如果要找负数，还得返回None。然后又发现只有第一个起始点能返回1，其他点都只能返回None，毕竟起点只有左上角，而不是任意边界的可能性。
- DP_positive其实是包括0的，返回的结果是可以包含0的。在grid[i][j]为负数的情况下，本来觉得只有找负数相乘才能得到正数，但其实有0也行。因此就算dp_negative[i-1][j]和dp_negative[i][j-1]都不存在，仍然可以通过DP_positive为0的情况，得到dp_positive的数值。
- 只要矩阵里有1个0存在，结果至少就是0，而不会是-1。dp_positive一路记录的都是最大的值，曾经在某条路上出现的0一般都会被抛弃掉。那么当遇到最后一个值是负值，如果此时dp_negative不存在，结果可能就是不存在了。但考虑到一路上被抛弃的0，结果反而应该是0。
于是在上面一堆坑的条件下，又要考虑正值负值零值，又要考虑存在和不存在None,结果就是不停的有bug。一个自以为轻车熟路的动态规划问题，花了半个多小时都没通过测试，直到比赛结束才打完了补丁通过。
赛后看了一下别人的版本，并没有非要考虑DP矩阵为正值还是负值，仅仅考虑最大值和最小值。毕竟最后只要考虑是否正数即可。 我也是纠结过一段时间，但还是按照稳妥的正值负值来区分了，没想到越写坑越多。
class Solution:
def maxProductPath(self, grid: List[List[int]]) -> int:
r, c = len(grid), len(grid[0])
dp_neg = [[""] * c for _ in range(r)]
dp_pos = [[""] * c for _ in range(r)]
mod = 10 ** 9 + 7
def maxPP(i, j, reqPos):
if ((i == -1 and j == 0) or (i == 0 and j == -1)) and reqPos:
return 1
if i < 0 or j < 0:
return None
if reqPos and dp_pos[i][j] != "":
return dp_pos[i][j]
elif (not reqPos) and dp_neg[i][j] != "":
return dp_neg[i][j]
upper_pos = maxPP(i - 1, j, reqPos=True)
upper_neg = maxPP(i - 1, j, reqPos=False)
left_pos = maxPP(i, j - 1, reqPos=True)
left_neg = maxPP(i, j - 1, reqPos=False)
neg_choices = [i for i in [upper_neg, left_neg] if i is not None]
pos_choices = [i for i in [upper_pos, left_pos] if i is not None]
# print(i, j, pos_choices, neg_choices)
if grid[i][j] < 0:
if not len(neg_choices):
dp_pos[i][j] = None
### 负数和0还是可以形成非负数
if len(pos_choices) and min(pos_choices) == 0:
dp_pos[i][j] = 0
else:
dp_pos[i][j] = min(neg_choices) * grid[i][j]
if not len(pos_choices):
dp_neg[i][j] = None
else:
dp_neg[i][j] = max(pos_choices) * grid[i][j]
elif grid[i][j] > 0:
if not len(neg_choices):
dp_neg[i][j] = None
else:
dp_neg[i][j] = min(neg_choices) * grid[i][j]
if not len(pos_choices):
dp_pos[i][j] = None
else:
dp_pos[i][j] = max(pos_choices) * grid[i][j]
elif grid[i][j] == 0:
dp_neg[i][j] = None
# if not len(pos_choices):
# dp_pos[i][j] = None
# else:
# dp_pos[i][j] = 0
dp_pos[i][j] = 0
if reqPos:
return dp_pos[i][j]
else:
return dp_neg[i][j]
maxv = maxPP(r - 1, c - 1, True)
print(dp_pos)
print(dp_neg)
if maxv is None:
for i in range(r):
for j in range(c):
if grid[i][j] == 0:
return 0
return -1
return maxv % mod