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

# 0064. Minimum Path Sum

<https://leetcode.com/problems/minimum-path-sum>

## Description

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:**

![](https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg)

```
**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`

## ac

```java
class Solution {
    public int minPathSum(int[][] grid) {
        // edge cases
        if (grid == null || grid.length == 0 || grid[0].length == 0) 
            return 0;

        int row = grid.length;
        int col = grid[0].length;
        // init
        for (int r = 1; r < row; r++) {
            grid[r][0] += grid[r-1][0];
        }
        for (int c = 1; c < col; c++) {
            grid[0][c] += grid[0][c-1];
        }

        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];
    }
}
```