Problems/0064. (M) Minimum Path Sum/Java/solution.java
class Solution {
  public int minPathSum(int[][] grid) {
    // bottom-up dynamic programming (tabulation)

    int n = grid.length;
    int m = grid[0].length;

    // value of dp[i][j] is sum of minimum path from grid[0][0] to grid[i][j]
    int[][] dp = new int[n][m];
    dp[0][0] = grid[0][0];
    for (int i = 1; i < n; i++)
      dp[i][0] = dp[i-1][0] + grid[i][0];
    for (int i = 1; i < m; i++)
      dp[0][i] = dp[0][i-1] + grid[0][i];

    // fill dp towards bottom-right
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < m; j++) {
        dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
      }
    }
    return dp[n-1][m-1];
  }
}
