# 62. Unique Paths

### Leetcode

<https://leetcode.com/problems/unique-paths/description/>

### 題目

There is a robot on an `m x n` grid. The robot is initially located at the **top-left corner** (i.e., `grid[0][0]`). The robot tries to move to the **bottom-right corner** (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time.

Given the two integers `m` and `n`, return *the number of possible unique paths that the robot can take to reach the bottom-right corner*.

The test cases are generated so that the answer will be less than or equal to `2 * 109`.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png)

<pre><code><strong>Input: m = 3, n = 7
</strong><strong>Output: 28
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: m = 3, n = 2
</strong><strong>Output: 3
</strong><strong>Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
</strong>1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
</code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - DP**

範例：`m = 3, n = 2`

使用 `dp[i][j]` 代表走到 `i + 1` 列 `j + 1` 行時所有可能的步數，從左上角開始走：

* `dp[0][0] = 1`

  第一列第一行為起始點，只有一種可能 => `dp[0][0] = 1`
* `dp[1][0] = 1`

  走到第二列第一行唯一的可能性為起始點往下走，也就是說 `dp[1][0] = dp[0][0] = 1`
* `dp[2][0] = 1`

  走到第三列第一行唯一的可能性為 `dp[1][0]` 往下走，也就是說 `dp[2][0] = dp[1][0] = 1`
* `dp[0][1] = 1`

  走到第一列第二行唯一的可能性為起始點往右走，也就是說 `dp[0][1] = dp[0][0] = 1`
* `dp[1][1] = 2`

  走到第二列第二行的可能性為 `dp[1][0]` 往右走以及 `dp[0][1]` 往下走，也就是說&#x20;

  `dp[1][1] = dp[1][0] + dp[0][1] = 1 + 1 = 2`
* `dp[2][1] = 3`

  走到第三列第二行的可能性為 `dp[2][0]` 往右走以及 `dp[1][1]` 往下走，也就是說&#x20;

  `dp[2][1] = dp[2][0] + dp[1][1] = 1 + 2 = 3`

```javascript
var uniquePaths = function (m, n) {
    const dp = Array.from({ length: m }, () => []);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 && j === 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = 0;
                // 如果 i - 1 沒有超過上面邊界的話，加入上面那個點的 DP
                if (i - 1 >= 0) {
                    dp[i][j] += dp[i - 1][j];
                }
                // 如果 j - 1 沒有超過左邊邊界的話，加入左邊那個點的 DP
                if (j - 1 >= 0) {
                    dp[i][j] += dp[i][j - 1];
                }
            }
        }
    }

    return dp[m - 1][n - 1];
};
```

**參考資料**

{% embed url="<https://leetcode.wang/leetCode-62-Unique-Paths.html>" %}
