Minimum Path Sum

In dynamic programming, the Minimum Path Sum problem involves finding the minimum cost to reach the bottom-right corner of a grid from the top-left corner. Each cell in the grid represents the cost of moving to that cell. We can only move down or right.

Let's consider a simple example. Suppose we have the following grid:

1grid = [
2  [1, 3, 1],
3  [1, 5, 1],
4  [4, 2, 1]
5]

To find the minimum path sum, we can use a dynamic programming approach. We can create a 2D array dp of the same size as the grid, where dp[i][j] represents the minimum cost to reach cell (i, j). We initialize dp[0][0] to the value of the top-left cell in the grid.

Then, we iterate through the grid starting from the second row, updating the values of dp[i][j] by taking the minimum between dp[i-1][j] and dp[i][j-1] and adding the cost of the current cell. This represents the minimum cost to reach the current cell from either the cell above or the cell to the left.

Finally, the value at the bottom-right corner of dp represents the minimum path sum.

Here's the Java code to solve the Minimum Path Sum problem using dynamic programming:

1import java.util.Arrays;
2
3class MinimumPathSum {
4  public static int minPathSum(int[][] grid) {
5    int m = grid.length;
6    int n = grid[0].length;
7    int[][] dp = new int[m][n];
8
9    dp[0][0] = grid[0][0];
10
11    for (int i = 1; i < m; i++) {
12      dp[i][0] = dp[i-1][0] + grid[i][0];
13    }
14
15    for (int j = 1; j < n; j++) {
16      dp[0][j] = dp[0][j-1] + grid[0][j];
17    }
18
19    for (int i = 1; i < m; i++) {
20      for (int j = 1; j < n; j++) {
21        dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
22      }
23    }
24
25    return dp[m-1][n-1];
26  }
27
28  public static void main(String[] args) {
29    int[][] grid = {
30      {1, 3, 1},
31      {1, 5, 1},
32      {4, 2, 1}
33    };
34
35    int minSum = minPathSum(grid);
36    System.out.println("Minimum Path Sum: " + minSum);
37  }
38}