> For the complete documentation index, see [llms.txt](https://tonyding.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tonyding.gitbook.io/algorithm/lc-64-minimum-path-sum.md).

# LC 64 Minimum Path Sum(M)

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.

`public int minPathSum(int[][] grid)`

**边界条件** 保证数组有行列

## 解题思路  DP

因为不能左或上， 所以 grid\[r]\[c] = min(grid\[r-1]\[c], grip\[r]\[c-1]) + grid\[r]\[c]

```java
public int minPathSum(int[][] grid) {
    int row = grid.length;
    if(row<1)
        return 0;
    int col = grid[0].length;
    for(int i = 1; i< col; i++){
        grid[0][i] += grid[0][i-1] ;
    }
    for(int j = 1; j< row; j++){
        grid[j][0] += grid[j-1][0] ;
    }
    for(int r = 1;r < row; r++){
        for(int c = 1; c< col; c++){
            grid[r][c] += Math.min(grid[r-1][c], grid[r][c-1]);
        }
    }
    return grid[row-1][col-1];
}
```