> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/ix.-dynamic-programming/64.-minimum-path-sum.md).

# 64. Minimum Path Sum

\# Medium

{% hint style="success" %}
Is very similar to #62.

1\. minPath represents minimum path instead of possible paths. 

2\. minPath initilizes each edge element: minPath\[x]\[y]=grid\[x]\[y].
{% endhint %}

### Solution:

1. Initilize `minPath[0][0] = grid[0][0]`
2. Initilize the edge elements of minPath: `minPath[x][y] = grid[x][y]+grid[0][0]`
3. Initilize other elements of minPath: `minPath[x][y] = min(minPath[x-1][y], minPath[x][y-1]) + grid[x][y]`

{% tabs %}
{% tab title="Java(O(mn)" %}

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

{% endtab %}

{% tab title="Python" %}

```python
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # initialize minPath
        m = len(grid)
        n = len(grid[m-1])
        minPath = [[-1]*n for i in range(m)]
        minPath[0][0] = grid[0][0]
        
        # initialize fixed part of minPath
        for x in range(1, m):
            minPath[x][0] = grid[x][0] + minPath[x-1][0]
        for y in range(1, n):
            minPath[0][y] = grid[0][y] + minPath[0][y-1]
            
        # compute other element of minPath
        for x in range(1, m):
            for y in range(1, n):
                minPath[x][y] = min(minPath[x-1][y], minPath[x][y-1]) + grid[x][y]
                
        return minPath[m-1][n-1]
```

{% endtab %}
{% endtabs %}