Minimum Path Sum

1public int minPathSum(int[][] grid) {
2    int m = grid.length;
3    int n = grid[0].length;
4    int[][] dp = new int[m][n];
5
6    // Initialize the first cell
7    dp[0][0] = grid[0][0];
8
9    // Fill the first column
10    for (int i = 1; i < m; i++) {
11        dp[i][0] = dp[i-1][0] + grid[i][0];
12    }
13
14    // Fill the first row
15    for (int j = 1; j < n; j++) {
16        dp[0][j] = dp[0][j-1] + grid[0][j];
17    }
18
19    // Fill the rest of the dp table
20    for (int i = 1; i < m; i++) {
21        for (int j = 1; j < n; j++) {
22            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
23        }
24    }
25
26    return dp[m-1][n-1];
27}