Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which the total cost incurred is minimum. From the cell (i,j) we can go (i,j-1), (i, j+1), (i-1, j), (i+1, j).
Note: It is assumed that negative cost cycles do not exist in the input matrix.
public int minimumCostPath(int[][] grid)
{
int n = grid.length;
int[][] mem = new int[n][n];
return minimumCostPath(grid, n, 0, 0, mem);
}
public int minimumCostPath(int[][] grid, int n, int row, int col, int[][] mem)
{
if (row == n - 1 && col == n - 1)
return grid[row][col];
if (mem[row][col] > 0)
return mem[row][col];
int temp = grid[row][col];
grid[row][col] = -1; //to prevent visiting same cell more than one time for a single path
int up = (int)(1e9);
int down = (int)(1e9);
int left = (int)(1e9);
int right = (int)(1e9);
if (row - 1 >= 0 && grid[row - 1][col] != -1)
up = minimumCostPath(grid, n, row - 1, col, mem);
if (row + 1 < n && grid[row + 1][col] != -1)
down = minimumCostPath(grid, n, row + 1, col, mem);
if (col - 1 >= 0 && grid[row][col - 1] != -1)
left = minimumCostPath(grid, n, row, col - 1, mem);
if (col + 1 < n && grid[row][col + 1] != -1)
right = minimumCostPath(grid, n, row, col + 1, mem);
mem[row][col] = temp + Math.min(up, Math.min(down, Math.min(left, right)));
grid[row][col] = temp; //revert the cell value in backtracking to find other paths
return mem[row][col];
}
The above code without memoization is giving me correct output but with memoization is giving me wrong output
Example:
9 7 6 2 4
4 3 5 8 9
9 1 1 1 9
3 5 7 5 2
3 5 1 3 4
Correct O/P: 30 (without memoization) Wrong O/P: 37 (with memoization)
Can someone help me to find what is wrong with my memoization implementation