Medium

题目描述

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

在所有从左上角 (0, 0) 开始，到右下角 (m - 1, n - 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)。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 15
  • -4 <= grid[i][j] <= 4

解题思路

这道题需要找到从左上角到右下角的路径，使得路径上所有数字的乘积最大且非负。

核心思路： 由于乘积可能为正也可能为负，我们需要同时维护两个值：到达每个位置时的最大乘积和最小乘积。这是因为负数乘以负数会变成正数，所以最小的负数在遇到另一个负数时可能变成最大的正数。

动态规划状态设计：

  • maxDP[i][j]：表示到达位置 (i,j) 的路径中乘积的最大值
  • minDP[i][j]：表示到达位置 (i,j) 的路径中乘积的最小值

状态转移： 对于每个位置 (i,j)，我们可以从上方 (i-1,j) 或左方 (i,j-1) 到达。当前位置的值为 grid[i][j]，则：

  • 如果 grid[i][j] >= 0：
    • maxDP[i][j] = max(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j]
    • minDP[i][j] = min(minDP[i-1][j], minDP[i][j-1]) * grid[i][j]
  • 如果 grid[i][j] < 0：
    • maxDP[i][j] = min(minDP[i-1][j], minDP[i][j-1]) * grid[i][j]
    • minDP[i][j] = max(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j]

最终检查右下角的最大乘积是否非负，如果是则返回结果对模取余，否则返回 -1。

代码实现

class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        const int MOD = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        
        vector<vector<long long>> maxDP(m, vector<long long>(n));
        vector<vector<long long>> minDP(m, vector<long long>(n));
        
        maxDP[0][0] = minDP[0][0] = grid[0][0];
        
        // Initialize first row
        for (int j = 1; j < n; j++) {
            maxDP[0][j] = minDP[0][j] = maxDP[0][j-1] * grid[0][j];
        }
        
        // Initialize first column
        for (int i = 1; i < m; i++) {
            maxDP[i][0] = minDP[i][0] = maxDP[i-1][0] * grid[i][0];
        }
        
        // Fill the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                long long a = maxDP[i-1][j] * grid[i][j];
                long long b = maxDP[i][j-1] * grid[i][j];
                long long c = minDP[i-1][j] * grid[i][j];
                long long d = minDP[i][j-1] * grid[i][j];
                
                maxDP[i][j] = max({a, b, c, d});
                minDP[i][j] = min({a, b, c, d});
            }
        }
        
        return maxDP[m-1][n-1] >= 0 ? maxDP[m-1][n-1] % MOD : -1;
    }
};

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        MOD = 10**9 + 7
        m, n = len(grid), len(grid[0])
        
        max_dp = [[0] * n for _ in range(m)]
        min_dp = [[0] * n for _ in range(m)]
        
        max_dp[0][0] = min_dp[0][0] = grid[0][0]
        
        # Initialize first row
        for j in range(1, n):
            max_dp[0][j] = min_dp[0][j] = max_dp[0][j-1] * grid[0][j]
        
        # Initialize first column
        for i in range(1, m):
            max_dp[i][0] = min_dp[i][0] = max_dp[i-1][0] * grid[i][0]
        
        # Fill the dp table
        for i in range(1, m):
            for j in range(1, n):
                a = max_dp[i-1][j] * grid[i][j]
                b = max_dp[i][j-1] * grid[i][j]
                c = min_dp[i-1][j] * grid[i][j]
                d = min_dp[i][j-1] * grid[i][j]
                
                max_dp[i][j] = max(a, b, c, d)
                min_dp[i][j] = min(a, b, c, d)
        
        return max_dp[m-1][n-1] % MOD if max_dp[m-1][n-1] >= 0 else -1

public class Solution {
    public int MaxProductPath(int[][] grid) {
        const int MOD = 1000000007;
        int m = grid.Length, n = grid[0].Length;
        
        long[,] maxDP = new long[m, n];
        long[,] minDP = new long[m, n];
        
        maxDP[0, 0] = minDP[0, 0] = grid[0][0];
        
        // Initialize first row
        for (int j = 1; j < n; j++) {
            maxDP[0, j] = minDP[0, j] = maxDP[0, j-1] * grid[0][j];
        }
        
        // Initialize first column
        for (int i = 1; i < m; i++) {
            maxDP[i, 0] = minDP[i, 0] = maxDP[i-1, 0] * grid[i][0];
        }
        
        // Fill the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                long a = maxDP[i-1, j] * grid[i][j];
                long b = maxDP[i, j-1] * grid[i][j];
                long c = minDP[i-1, j] * grid[i][j];
                long d = minDP[i, j-1] * grid[i][j];
                
                maxDP[i, j] = Math.Max(Math.Max(a, b), Math.Max(c, d));
                minDP[i, j] = Math.Min(Math.Min(a, b), Math.Min(c, d));
            }
        }
        
        return maxDP[m-1, n-1] >= 0 ? (int)(maxDP[m-1, n-1] % MOD) : -1;
    }
}

var maxProductPath = function(grid) {
    const MOD = 1e9 + 7;
    const m = grid.length, n = grid[0].length;
    
    const maxDP = Array(m).fill(null).map(() => Array(n).fill(0));
    const minDP = Array(m).fill(null).map(() => Array(n).fill(0));
    
    maxDP[0][0] = minDP[0][0] = grid[0][0];
    
    // Initialize first row
    for (let j = 1; j < n; j++) {
        maxDP[0][j] = minDP[0][j] = maxDP[0][j-1] * grid[0][j];
    }
    
    // Initialize first column
    for (let i = 1; i < m; i++) {
        maxDP[i][0] = minDP[i][0] = maxDP[i-1][0] * grid[i][0];
    }
    
    // Fill the dp table
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            const a = maxDP[i-1][j] * grid[i][j];
            const b = maxDP[i][j-1] * grid[i][j];
            const c = minDP[i-1][j] * grid[i][j];
            const d = minDP[i][j-1] * grid[i][j];
            
            maxDP[i][j] = Math.max(a, b, c, d);
            minDP[i][j] = Math.min(a, b, c, d);
        }
    }
    
    return maxDP[m-1][n-1] >= 0 ? maxDP[m-1][n-1] % MOD : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n)，需要遍历整个矩阵一次
空间复杂度O(m × n)，使用两个二维数组存储最大值和最小值