算法：64. Minimum Path Sum最小路径和

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

动态规划解法

考虑3条路径：

1. row第一行路径，挨个累加dp[r][0] = dp[r - 1][0] + grid[r][0];
2. column第一列路径，挨个累加dp[0][c] = dp[0][c - 1] + grid[0][c];
3. 非边缘路径，当前值 dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);

最终结果为dp的最后一个值dp[grid.length - 1][grid[0].length - 1]

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        
        for (int r = 1; r < grid.length; r++) {
            dp[r][0] = dp[r - 1][0] + grid[r][0];
        }
        
        for (int c = 1; c < grid[0].length; c++) {
            dp[0][c] = dp[0][c - 1] + grid[0][c];
        }
        
        for (int r = 1; r < grid.length; r++) {
            for (int c = 1; c < grid[0].length; c++) {
                dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);
            }
        }
        
        return dp[grid.length - 1][grid[0].length - 1];
    }
}