Minimum Cost Path Recursion - Memoization

59 Views Asked by At

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

0

There are 0 best solutions below