LEETCODE 1594. Maximum Non Negative Product in a Matrix 解题思路分析

题目大意:

矩阵的最大非负积

给你一个大小为 rows x cols 的矩阵 grid 。最初,你位于左上角 (0, 0) ,每一步,你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中,找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 109 + 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1594

解题思路分析:

这是一点典型的动态规划题目,对于DP题目我比较喜欢使用递归方式来解题。本题也不例外,实际上使用递归方式解DP题目与dfs深度优先搜索的思路非常类似。以本题为例,由于我们无法一眼看出哪一种路线的乘积最大,因此,我们必须尝试走完每一条路线后才能做出比较。dfs递归方式的核心即是遍历每一条路径。

如果本题中不包含负数,将是一道非常简单的题目,但由于负数的存在,最大非负数乘积并不一定是多个正数的乘积,也有可能是偶数个负数的乘积。因此递归时,我们需要2个记忆数组,来保存当前路径中的最大乘积,与最小乘积(如果最小乘积与当前数字都是负数时,他们的乘积可能会是最大值)。注意这里的最大乘积与最小乘积都有可能是正数或者负数亦或者是0,解题时我们分别将他们与当前数字相乘,再使用得到的结果分别更新当前最大值与最小值。

dfs递归中,对于当前点,在不越界的前提下,我们可以向下走,或者向右走。因此,当前点到达终点的最大乘积将在下面4中可能中产生:

max[r][c]=Math.max(max[r+1][c]*grid[r][c],max[r][c]); // 下一步到达终点的最大乘积与当前数字乘积
max[r][c]=Math.max(min[r+1][c]*grid[r][c],max[r][c]); // 下一步到达终点的最小乘积与当前数字乘积
max[r][c]=Math.max(max[r][c+1]*grid[r][c],max[r][c]); // 右一步到达终点的最大乘积与当前数字乘积
max[r][c]=Math.max(min[r][c+1]*grid[r][c],max[r][c]); // 右一步到达终点的最小乘积与当前数字乘积

同理当前点到终点的最小乘积也将在上述4重结果中产生。其中max[r+1][c],min[r+1][c],max[r][c+1],min[r][c+1]将在递归子函数中取得。递归的结束条件为当前点为终点时(右下角),当前点到终点(也就是自身)的最大乘积与最小成绩都是当前点的数值。

最终我们求解的是起点到终点的最大乘积,如果该乘积为负数,返回-1。

实现代码:

Long[][] max;
Long[][] min;
public int maxProductPath(int[][] grid) {
    max=new Long[grid.length][grid[0].length];
    min=new Long[grid.length][grid[0].length];
    help(grid,0,0);
    if(max[0][0]<0) return -1;
    return (int)(max[0][0]%1000000007);
}

void help(int[][] grid, int r, int c){
    if(r==grid.length-1&&c==grid[0].length-1){ // 当前点为终点
        max[r][c]=(long)grid[r][c];
        min[r][c]=(long)grid[r][c];
        return;
    }
    if(max[r][c]!=null) return; // 当前点已经递归过
    max[r][c]=Long.MIN_VALUE;
    min[r][c]=Long.MAX_VALUE;
    if(r+1<grid.length){ // 可以向下走
        help(grid, r+1, c);
        // 更新最大值为下一步到达终点的最大乘积与当前数字乘积
        max[r][c]=Math.max(max[r+1][c]*grid[r][c],max[r][c]);
        // 更新最大值为下一步到达终点的最小乘积与当前数字乘积
        max[r][c]=Math.max(min[r+1][c]*grid[r][c],max[r][c]);
        // 更新最小值为下一步到达终点的最大乘积与当前数字乘积
        min[r][c]=Math.min(max[r+1][c]*grid[r][c],min[r][c]);
        // 更新最小值为下一步到达终点的最小乘积与当前数字乘积
        min[r][c]=Math.min(min[r+1][c]*grid[r][c],min[r][c]);
    }
    if(c+1<grid[0].length){ // 可以向右走
        help(grid, r, c+1);
        // 更新最大值为右一步到达终点的最大乘积与当前数字乘积
        max[r][c]=Math.max(max[r][c+1]*grid[r][c],max[r][c]);
        // 更新最大值为右一步到达终点的最小乘积与当前数字乘积
        max[r][c]=Math.max(min[r][c+1]*grid[r][c],max[r][c]);
        // 更新最小值为右一步到达终点的最大乘积与当前数字乘积
        min[r][c]=Math.min(max[r][c+1]*grid[r][c],min[r][c]);
        // 更新最小值为右一步到达终点的最小乘积与当前数字乘积
        min[r][c]=Math.min(min[r][c+1]*grid[r][c],min[r][c]);
    }
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 50.00% of Java online submissions for Maximum Non Negative Product in a Matrix.

Memory Usage: 41.5 MB, less than 25.00% of Java online submissions for Maximum Non Negative Product in a Matrix.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1594-maximum-non-negative-product-in-a-matrix-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。