LeetCode矩阵最大非负乘积：回溯解法超时优化求助

• 解决矩阵最大非负乘积题目时，自行编写的递归回溯解法在大规模矩阵用例下运行失败，判断存在重复计算但无法定位冗余点
• 待解决两个核心问题：
  1. 哪些状态需要做记忆化（memoize）存储
  2. 如何调整现有逻辑，实现每一步的最优决策
• 当前实现代码如下：

class Solution {
    private long max = -1;
    public int maxProductPath(int[][] grid) {
        long mod=1000000007;
        int rows = grid.length;
        int cols = grid[0].length;
        int cp = 1;
        pathFinder(grid, rows, cols, cp, rows-1, cols-1);
        if(max < 0 ) return -1;
        return (int)(max % mod);
    }
    
    public void pathFinder(int[][]grid, int rows, int cols, long cp, int r, int c){
        if(r >= rows || c >= cols || r < 0 || c < 0){
            return;
        }
        if(r == 0 && c  == 0){
            this.max = Math.max(cp * grid[r][c] , this.max);
            return;
        }
        pathFinder(grid, rows, cols, cp * grid[r][c], r - 1, c);
        pathFinder(grid, rows, cols, cp * grid[r][c], r , c - 1);
    }
}

当前纯回溯写法的时间复杂度为O(2^(m+n))，本质是枚举所有从终点到起点的合法路径，没有做任何状态缓存。重复计算的核心是：多次递归进入同一坐标(r,c)时，无论之前累积的乘积是多少，都会重新向起点方向遍历所有分支，产生大量无用计算。矩阵行列数超过15时路径总数就会达到百万级，必然触发超时。

1. 记忆化状态定义 #

不需要缓存路径上的累积乘积，只需要为每个坐标(r,c)存储两个值即可：

• minProd[r][c]：从(r,c)出发走到左上角(0,0)能得到的最小乘积
• maxProd[r][c]：从(r,c)出发走到左上角(0,0)能得到的最大乘积
  之所以要同时存最小值，是因为矩阵中存在负数和0：如果当前格子值为负数，乘上之前路径的最小负数（绝对值最大的负数），反而可能得到全局最大的乘积；如果只存最大值，会完全漏掉这类最优解。

2. 递推逻辑调整 #

把原来无返回值的回溯函数，改成返回长度为2的long数组（第一个元素存当前位置的最小乘积，第二个存最大乘积），按以下规则计算：

• 边界1：坐标越界时，直接返回无效值，不参与后续计算
• 边界2：走到左上角(0,0)时，最小、最大乘积都是grid[0][0]，直接返回该值即可
• 普通位置：分别递归计算向上走(r-1,c)、向左走(r,c-1)的最小、最大乘积，把这四个值（向上的最小/最大、向左的最小/最大）分别乘上当前格子的数值grid[r][c]，从四个结果里取最小值作为minProd[r][c]，取最大值作为maxProd[r][c]，存入缓存后返回。
• 每次进入递归函数先检查缓存，如果当前(r,c)已经计算过，直接返回缓存值，不要重复递归。

3. 最终结果处理 #

递归计算完终点(rows-1, cols-1)的最大乘积后，如果值小于0直接返回-1，否则对10^9+7取模返回即可。全程用long类型存储乘积，避免整数溢出。

内容的提问来源于stack exchange，提问作者Spindoctor