1594. 矩阵的最大非负积.md

1594. 矩阵的最大非负积

• 动态规划

/**
 *
 * @description 令dp[row][col]存储从(0, 0)到(row, col)点的最大乘积和最小乘积,再用动态规划,转移方程见代码!
 * @param {number[][]} grid
 * @return {*}  {number}
 */
function maxProductPath(grid: number[][]): number {

    const rows: number = grid.length,
        cols: number = grid[0].length,
        dp: GridNode[][] = new Array(rows).fill(null).map(() => new Array(cols));

    for (let row = 0; row < rows; ++row) {
        let max: number, min: number;
        for (let col = 0; col < cols; ++col) {
            if (!row && !col) {
                max = min = grid[row][col];
            } else if (!row) {
                max = Math.max(
                    dp[row][col - 1].max * grid[row][col],
                    dp[row][col - 1].min * grid[row][col],
                );
                min = Math.min(
                    dp[row][col - 1].max * grid[row][col],
                    dp[row][col - 1].min * grid[row][col],
                );
            } else if (!col) {
                max = Math.max(
                    dp[row - 1][col].max * grid[row][col],
                    dp[row - 1][col].min * grid[row][col],
                );
                min = Math.min(
                    dp[row - 1][col].max * grid[row][col],
                    dp[row - 1][col].min * grid[row][col],
                );
            } else {
                max = Math.max(
                    dp[row][col - 1].max * grid[row][col],
                    dp[row][col - 1].min * grid[row][col],
                    dp[row - 1][col].max * grid[row][col],
                    dp[row - 1][col].min * grid[row][col],
                );
                min = Math.min(
                    dp[row][col - 1].max * grid[row][col],
                    dp[row][col - 1].min * grid[row][col],
                    dp[row - 1][col].max * grid[row][col],
                    dp[row - 1][col].min * grid[row][col],
                );
            }
            dp[row][col] = { max, min };
        }
    }

    return dp[rows - 1][cols - 1].max >= 0
        ? dp[rows - 1][cols - 1].max % (10 ** 9 + 7) : -1;
};

interface GridNode {
    max: number,
    min: number,
}