> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/niu-ke-0059-zhong-deng-ju-zhen-de-zui-xiao-lu-jing-he.md).

# 矩阵的最小路径和

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/pages/R5NyOzkn3qAZy7wCx1pS#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/pages/R5NyOzkn3qAZy7wCx1pS#动态规划)

> [矩阵的最小路径和\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb)

**问题简述**

```
给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
```

**思路**

* 定义 `dp(i,j)` 表示到达 `m[i][j]` 最短距离；
* 递推公式：`dp(i,j) = m[i][j] + min(dp(i-1,j), dp(i,j-1))`；
* 初始化：
  * `dp(i,0)=sum(m[:i][]0)`
  * `dp(0,j)=sum(m[0][:j])`；

<details>

<summary><strong>递归写法</strong></summary>

```python
class Solution:
    def minPathSum(self, matrix: List[List[int]]) -> int:
        
        import sys
        sys.setrecursionlimit(100000)
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dfs(i, j):
            if i == 0 and j == 0: return matrix[i][j]
            if i == 0: return sum(matrix[i][j] for j in range(j + 1))
            if j == 0: return sum(matrix[i][j] for i in range(i + 1))
            
            return matrix[i][j] + min(dfs(i - 1, j), dfs(i, j - 1))
        
        m, n = len(matrix), len(matrix[0])
        return dfs(m - 1, n - 1)
```

</details>

<details>

<summary><strong>迭代写法（略）</strong></summary>

```python
```

</details>