I am trying to solve the following problem on leetcode.com

I found a resource asking a similar question but it didn't yield anything plausible.

I am able to come up with a recursive backtracking solution but it fails the last 5 test cases for a very large matrix. I sense there is some repetitive work but can't tell what it is.

The way the logic is written, I am struggling to find out

1. What I need to memoize
2. How to tailor my logic so that I am optimizing at each step

Any help is appreciated

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);
    }
}

CodePudding user response：

Your logic is correct, but since you're not using memoization, multiple repeated calls lead to a timeout.

You basically need to memoize the max product for a path starting at (r,c), so your function would look like

pathFinder(...args, dp[][]) {
  if (dp[row][col] != null) return dp[row][col]
  else {
    // compute answer
    dp[row][col] = answer
  }
}

CodePudding user response：

This seems to be a little twist on the classic right-down dynamic program. The problem is that we need two states because our maximum could be constructed from two positives or two negatives. Generally:

if grid[i][j] < 0:
  dp[i][j][positive] = grid[i][j]
    * min(
        dp[i-1][j][negative],
        dp[i][j-1][negative]
      )
  dp[i][j][negative] = grid[i][j]
    * max(
        dp[i-1][j][positive],
        dp[i][j-1][positive]
      )

if grid[i][j] > 0:
  dp[i][j][positive] = grid[i][j]
    * max(
        dp[i-1][j][positive],
        dp[i][j-1][positive]
      )
  dp[i][j][negative] = grid[i][j]
    * min(
        dp[i-1][j][negative],
        dp[i][j-1][negative]
      )