魔法师 (@Constanline) 在 Leetcode每日一题 —— 1594. 矩阵的最大非负积 中发帖
思路
因为只能往右/下走,所以可以从左上开始遍历,用递推/动态规划求出走到每个格子的时候可能得到的最大正/负值。
代码
class Solution {
public int maxProductPath(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 是否可能是0
boolean z = grid[0][0] == 0;
// 存储走到每个格子的时候的可能最大值 0负 1正
long[][][] cache = new long[m][n][2];
// 初始化边界
cache[0][0][0] = Math.max(-grid[0][0], 0);
...