Maximum Product In Matrix

I was trying to calculate the maximum product that can be achieved when traveling from the top left of a 2D array to the bottom right.

I know there is a solution here that uses dynamic programming in a bottom up manner (i.e. iterative for loops here: https://www.byte-by-byte.com/matrixproduct/)

I was attempting to do this using recursive backtracking and memoization.

It seems my code below works with just recursive backtracking, but once I try memoizing I get incorrect results. I think I am overlooking something and a second look would be appreciated.

Below is the code when it does not work:

//greatest product
//i row
//j col
let myMatrix = 
[
    [1,2,3],
    [4,5,6],
    [7,8,9],
]

let myMemo = new Array(3).fill(new Array(3).fill(null));
console.log(myMemo[0][1]);


function greatestPath(i,j, matrix, memo){
    //Memo Object {product, pathArray}
    //Check Memo Table
    if(i == matrix.length - 1 && j == matrix[0].length - 1 && memo[i][j] != null){
        return memo[i][j];
    }

    console.log("Processing: ", matrix[i][j]);
    //Base Case
    if(i == matrix.length - 1 && j == matrix[0].length - 1){
        return {
            product: matrix[i][j], 
            path: new Array()
        };
    }


    //Working Logic
    let result = 
        {
            product: 0, 
            path: new Array()
        };

    let downResult = null;
    let downProduct = 0
    let rightResult = null;
    let rightProduct = 0;

    if(i + 1 < matrix.length){
        downResult = greatestPath(i + 1, j, matrix, memo);
        downProduct = matrix[i][j] * downResult.product;
    }
        

    if(j + 1 < matrix[0].length){
        rightResult = greatestPath(i, j + 1, matrix, memo);
        rightProduct = matrix[i][j] * rightResult.product;
    }


    if(downProduct > rightProduct){
        result.product = downProduct;
        result.path = [["D", matrix[i+1][j]], ...downResult.path ]
    }else{
        result.product = rightProduct;
        result.path = [["R", matrix[i][j+1]], ...rightResult.path ]
    }


    //Return
    memo[i][j] = result;
    return memo[i][j];
}

//
console.log(greatestPath(0,0,myMatrix, myMemo));

Output:

{ product: 11664, path: [
[ ‘R’, 2 ],
[ ‘R’, 3 ],
[ ‘D’, 6 ],
[ ‘D’, 9 ],
[ ‘D’, 9 ],
[ ‘D’, 9 ] ] }

Here is is working with just backtracking:

//greatest product
//i row
//j col
let myMatrix = 
[
    [1,2,3],
    [4,5,6],
    [7,8,9],
]

let myMemo = new Array(3).fill(new Array(3).fill(null));
console.log(myMemo[0][1]);


function greatestPath(i,j, matrix, memo){
    //Memo Object {product, pathArray}
    //Check Memo Table
    // if(i == matrix.length - 1 && j == matrix[0].length - 1 && memo[i][j] != null){
    //     return memo[i][j];
    // }

    console.log("Processing: ", matrix[i][j]);
    //Base Case
    if(i == matrix.length - 1 && j == matrix[0].length - 1){
        return {
            product: matrix[i][j], 
            path: new Array()
        };
    }


    //Working Logic
    let result = 
        {
            product: 0, 
            path: new Array()
        };

    let downResult = null;
    let downProduct = 0
    let rightResult = null;
    let rightProduct = 0;

    if(i + 1 < matrix.length){
        downResult = greatestPath(i + 1, j, matrix, memo);
        downProduct = matrix[i][j] * downResult.product;
    }
        

    if(j + 1 < matrix[0].length){
        rightResult = greatestPath(i, j + 1, matrix, memo);
        rightProduct = matrix[i][j] * rightResult.product;
    }


    if(downProduct > rightProduct){
        result.product = downProduct;
        result.path = [["D", matrix[i+1][j]], ...downResult.path ]
    }else{
        result.product = rightProduct;
        result.path = [["R", matrix[i][j+1]], ...rightResult.path ]
    }


    //Return
    //memo[i][j] = result;
    return result;
}

//
console.log(greatestPath(0,0,myMatrix, myMemo));

Output:

{ product: 2016, path: [ [ ‘D’, 4 ], [ ‘D’, 7 ], [ ‘R’, 8 ], [
‘R’, 9 ] ] }

Any help is appreciated.

Thanks

Source: Ask Javascript Questions

LEAVE A COMMENT