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    // Base case
7    dp[0][0] = grid[0][0];
8
9    // Fill first row
10    for (int j = 1; j < n; j++) {
11        dp[0][j] = dp[0][j - 1] + grid[0][j];
12    }
13
14    // Fill first column
15    for (int i = 1; i < m; i++) {
16        dp[i][0] = dp[i - 1][0] + grid[i][0];
17    }
18
19    // Fill rest of DP table
20    for (int i = 1; i < m; i++) {
21        for (int j = 1; j < n; j++) {
22            dp[i][j] = grid[i][j] + Math.min(
23                dp[i - 1][j],   // from top
24                dp[i][j - 1]    // from left
25            );
26        }
27    }
28
29    return dp[m - 1][n - 1];
30}