leetcode [64. 最小路径和](https://leetcode-cn.com/problems/minimum-path-sum/)

# leetcode [64. 最小路径和](https://leetcode-cn.com/problems/minimum-path-sum/)

给定一个包含非负整数的 `*m* x *n*` 网格 `grid` ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

**示例 1：**


```
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
```

**示例 2：**

```
输入：grid = [[1,2,3],[4,5,6]]
输出：12
```

**提示：**

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

Related Topics

数组

动态规划

矩阵

## 思路1：动态规划

参考第62题不同路径，这道题计算的从左上角到右下角的路径数之和。我们可以把dp中的路径数量改成从左上角到达这个点的最小路径和。

```java
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        int sum = 0;
        for(int i = 0 ; i < m;i++){
            sum += grid[i][0];
            dp[i][0] = sum;
        }
        sum = 0;
        for(int j = 0 ; j < n;j++){
            sum += grid[0][j];
            dp[0][j] = sum;
        }
        //dp[i][j] = (左边和上边的最小值) 加上当前节点的值
        for(int i = 1; i < m;i++){
            for(int j = 1; j < n;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}
解答成功:
            执行耗时:2 ms,击败了95.64% 的Java用户
            内存消耗:43.8 MB,击败了21.81% 的Java用户
```