0062. 不同路徑 · ttttt

# 0062. 不同路徑 ## 題目地址(62. 不同路徑) <https://leetcode-cn.com/problems/unique-paths/> ## 題目描述 ``` <pre class="calibre18">``` 一個機器人位于一個 m x n 網格的左上角（起始點在下圖中標記為“Start” ）。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。問總共有多少條不同的路徑？ ``` ``` ![](https://img.kancloud.cn/40/44/40448415f45922c7d79dc8fdad0832b9_400x183.jpg) ``` <pre class="calibre18">``` 例如，上圖是一個7 x 3 的網格。有多少可能的路徑？示例 1: 輸入: m = 3, n = 2 輸出: 3 解釋: 從左上角開始，總共有 3 條路徑可以到達右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右示例 2: 輸入: m = 7, n = 3 輸出: 28 提示： 1 <= m, n <= 100 題目數據保證答案小于等于 2 * 10 ^ 9 ``` ``` ## 前置知識 - 動態規劃 - 排列組合 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路首先這道題可以用排列組合的解法來解，需要一點高中的知識。 ![](https://img.kancloud.cn/c5/f2/c5f28c5e10a0a70354153d3ade87b844_1586x571.jpg) 而這道題我們用動態規劃來解。這是一道典型的適合使用動態規劃解決的題目，它和爬樓梯等都屬于動態規劃中最簡單的題目，因此也經常會被用于面試之中。讀完題目你就能想到動態規劃的話，建立模型并解決恐怕不是難事。其實我們很容易看出，由于機器人只能右移動和下移動，因此第\[i, j\]個格子的總數應該等于\[i - 1, j\] + \[i, j -1\]，因為第\[i,j\]個格子一定是從左邊或者上面移動過來的。 ![](https://img.kancloud.cn/f8/18/f818d67803be6dd98dac3988d397fac2_179x268.jpg) 代碼大概是： Python Code: ``` <pre class="calibre18">``` class Solution: def uniquePaths(self, m: int, n: int) -> int: d = [[1] * n for _ in range(m)] for col in range(1, m): for row in range(1, n): d[col][row] = d[col - 1][row] + d[col][row - 1] return d[m - 1][n - 1] ``` ``` **復雜度分析** - 時間復雜度：O(M?N)O(M \* N)O(M?N) - 空間復雜度：O(M?N)O(M \* N)O(M?N) 由于 dp\[i\]\[j\] 只依賴于左邊的元素和上面的元素，因此空間復雜度可以進一步優化，優化到 O(n). ![](https://img.kancloud.cn/f5/65/f56599f440cc34171462c451154f9abe_603x356.jpg) 具體代碼請查看代碼區。當然你也可以使用記憶化遞歸的方式來進行，由于遞歸深度的原因，性能比上面的方法差不少： > 直接暴力遞歸的話可能會超時。 Python3 Code: ``` <pre class="calibre18">``` class Solution: @lru_cache def uniquePaths(self, m: int, n: int) -> int: if m == 1 or n == 1: return 1 cnt = self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1) return cnt ``` ``` ## 關鍵點 - 排列組合原理 - 記憶化遞歸 - 基本動態規劃問題 - 空間復雜度可以進一步優化到 O(n), 這會是一個考點 ## 代碼代碼支持 JavaScript，Python3 JavaScript Code: ``` <pre class="calibre18">``` /* * @lc app=leetcode id=62 lang=javascript * * [62] Unique Paths * * https://leetcode.com/problems/unique-paths/description/ */ /** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths = function (m, n) { const dp = Array(n).fill(1); for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[j] = dp[j] + dp[j - 1]; } } return dp[n - 1]; }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [1] * n for _ in range(1, m): for j in range(1, n): dp[j] += dp[j - 1] return dp[n - 1] ``` ``` **復雜度分析** - 時間復雜度：O(M?N)O(M \* N)O(M?N) - 空間復雜度：O(N)O(N)O(N) ## 擴展你可以做到比O(M?N)O(M \* N)O(M?N)更快，比O(N)O(N)O(N)更省內存的算法么？這里有一份[資料](https://leetcode.com/articles/unique-paths/)可供參考。 > 提示：考慮數學 ## 相關題目 - [70. 爬樓梯](https://leetcode-cn.com/problems/climbing-stairs/) - [63. 不同路徑 II](63.unique-paths-ii.md)