> 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/62.-unique-paths.md).

# 62. Unique Paths

\# medium

{% hint style="success" %}
Using two-layer array to record paths for each grid start from right-down corner to left-up corner.
{% endhint %}

### Solution:

1. Initilize down and left parts of the grid with number of 1
2. Compute down-up or left-right grid based on known grid. `f(x,y) = f(x-1,y) + f(x,y-1)`

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

```java
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] paths = new int[m][n];
        for(int[] arr: paths)
            Arrays.fill(arr, 1);
        for(int i = 0; i < m; i ++)
            paths[i][0] = 1;
        
        for(int i = 1; i < m; i ++)
            for(int j = 1; j < n; j ++)
                paths[i][j] = paths[i-1][j] + paths[i][j-1];
        
        return paths[m-1][n-1];
    }
}
```

{% endtab %}

{% tab title="Python" %}

```python
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        paths = [[1] *n for i in range(m)]
        
        for i in range(1, m):
            for j in range(1, n):
                paths[i][j] = paths[i-1][j] + paths[i][j-1]
                
        return paths[-1][-1]
```

{% endtab %}
{% endtabs %}

{% hint style="danger" %}
这道题思路简单，但是要一次性写对很难，因为要非常清楚index，很容易错，右下角index为（0，0）；并且事先一定要定义好array记录的意义，记录的不是每一格到终点的步数，而是每一格到终点的路径的个数。
{% endhint %}