Minimum Path Sum - Java Solution

1. Introduction

In this post, we address a classic problem in dynamic programming and matrix manipulation - finding the minimum path sum in a grid. This problem involves navigating through a grid of non-negative numbers from the top-left corner to the bottom-right corner in such a way that the sum of the numbers along the path is minimized.

Problem

Given an m x n grid filled with non-negative numbers, the objective is to find a path from the top left to the bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

2. Solution Steps

1. Create a 2D array dp of the same dimensions as the grid to store the minimum path sums.

2. Initialize dp[0][0] with the value at the top-left corner of the grid.

3. Fill the first row and first column of dp by accumulating values from the grid.

4. For each remaining cell, calculate the minimum path sum as the minimum of the sum from the top or left cell plus the current cell's value.

5. The value at dp[m-1][n-1] will represent the minimum path sum to reach the bottom-right corner.

3. Code Program

public class MinimumPathSum {
    public static void main(String[] args) {
        int[][] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        System.out.println(minPathSum(grid)); // Test the function
    }

    // Function to find the minimum path sum
    public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        // Initialize the top-left cell
        dp[0][0] = grid[0][0];

        // Initialize first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        // Initialize first row
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // Fill the rest of the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
}

Output:

7

Explanation:

1. minPathSum: This function calculates the minimum path sum in an m x n grid. It uses a dynamic programming approach where dp[i][j] represents the minimum path sum to reach cell (i, j).

2. The function initializes dp[0][0] with the value from the top-left corner of the grid.

3. It then initializes the first row and first column of dp by accumulating the values from the grid, as there is only one way to reach these cells.

4. For each cell in the rest of the grid, the function computes the minimum path sum as the minimum of the sum from the top or left cell plus the current cell's value.

5. The bottom-right cell of dp, dp[m-1][n-1], holds the minimum path sum to reach the bottom-right corner of the grid.

6. This approach efficiently computes the minimum path sum by building up solutions from smaller subproblems.