// Runtime: 2 ms, faster than 90.36% of Java online submissions for Minimum Path Sum.
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];

        for (int r = m-1; r >= 0; r--) {
            dp[r][n-1] = grid[r][n-1] + (r + 1 < m ? dp[r+1][n-1]: 0);

            for (int c = n-2; c >= 0; c--)
                if (r + 1 < m) {
                    dp[r][c] = grid[r][c] + Math.min(dp[r+1][c], dp[r][c+1]);
                } else {
                    dp[r][c] = grid[r][c] + dp[r][c+1];
                }
        }

        return dp[0][0];
    }
}