Solve the Minimum Cost Path problem in a grid using dynamic programming.?

The Minimum Cost Path problem is a classic dynamic programming problem that involves finding the lowest cost path from the top-left corner of a grid to the bottom-right corner, while moving only down, right, and diagonally down-right.

To solve this problem using dynamic programming, we can create a grid of memoized values, where each cell represents the minimum cost to reach that cell from the top-left corner. We start by initializing the first row and first column with their cumulative values, since there is only one possible path to each cell in these lines.

Then, for each cell in the remaining part of the grid, we calculate the minimum cost to reach that cell by taking the minimum of the three neighboring cells: the cell above, the cell to the left, and the cell diagonally up and left. We add the cost of the current cell to the minimum of these three values to get the minimum cost path to that cell.

Finally, we return the memoized value in the bottom-right corner of the grid, which represents the minimum cost path to reach that point.

Here is an implementation of the Minimum Cost Path problem in Java:

public static int minCostPath(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] memo = new int[m][n];
    
    // initialize first row and first column
    memo[0][0] = grid[0][0];
    for (int i = 1; i < m; i++) {
        memo[i][0] = memo[i-1][0] + grid[i][0];
    }
    for (int j = 1; j < n; j++) {
        memo[0][j] = memo[0][j-1] + grid[0][j];
    }
    
    // fill in rest of memoized grid
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            memo[i][j] = grid[i][j] + Math.min(memo[i-1][j-1], Math.min(memo[i-1][j], memo[i][j-1]));
        }
    }
    
    // return bottom-right corner value
    return memo[m-1][n-1];
}

For example, if we have the following grid:

int[][] grid = {
    {1, 3, 5, 8},
    {4, 2, 1, 7},
    {4, 3, 2, 3}
};

The minimum cost path to reach the bottom-right corner is:

1 -> 3 -> 1 -> 2 -> 3

With a total cost of 8, which is returned by the ‘minCostPath‘ method.