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

function greatestPath(i,j, matrix, memo){
//Memo Object {product, pathArray}
//Check Memo Table
if(i == matrix.length - 1 && j == matrix.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.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.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);

function greatestPath(i,j, matrix, memo){
//Memo Object {product, pathArray}
//Check Memo Table
// if(i == matrix.length - 1 && j == matrix.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.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.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