class Solution {
    // 경로를 따라 모든 숫자의 합을 최소화하는 왼쪽 위에서 오른쪽 아래로 경로
    // 아래 또는 오른쪽으로만 이동할 수 있다.
    // T: O(mn)
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        int[][] dp = new int[m + 1][n + 1];
        for (int[] row: dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[m - 1][n] = 0;
        
        for (int r = m - 1; r >= 0; r--) {
            for (int c = n - 1; c >= 0; c--) {
                dp[r][c] = grid[r][c] + Math.min(dp[r + 1][c], dp[r][c + 1]);
            }
        }
        
        return dp[0][0];
    }
}