> 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/02/niu-ke-0034-jian-dan-qiu-lu-jing.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=%E7%AE%80%E5%8D%95\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/02/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/02/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/02/pages/R5NyOzkn3qAZy7wCx1pS#动态规划)

**问题简述**

```
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？
```

> [求路径\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358)

**思路：动态规矩**

<details>

<summary><strong>Python：递归</strong></summary>

```python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        # write code here
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == m and j == n:
                return 1
            if i > m or j > n: return 0
            
            return dp(i + 1, j) + dp(i, j + 1)
        
        return dp(1, 1)
```

</details>