<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 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">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">uniquePaths</span><span class="hljs-params">(self, m: int, n: int)</span> -> int:</span> d = [[<span class="hljs-params">1</span>] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m)] <span class="hljs-keyword">for</span> col <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, m): <span class="hljs-keyword">for</span> row <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): d[col][row] = d[col - <span class="hljs-params">1</span>][row] + d[col][row - <span class="hljs-params">1</span>] <span class="hljs-keyword">return</span> d[m - <span class="hljs-params">1</span>][n - <span class="hljs-params">1</span>] ``` ``` **復雜度分析** - 時間復雜度: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">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-params"> @lru_cache</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">uniquePaths</span><span class="hljs-params">(self, m: int, n: int)</span> -> int:</span> <span class="hljs-keyword">if</span> m == <span class="hljs-params">1</span> <span class="hljs-keyword">or</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> cnt = self.uniquePaths(m - <span class="hljs-params">1</span>, n) + self.uniquePaths(m, n - <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> cnt ``` ``` ## 關鍵點 - 排列組合原理 - 記憶化遞歸 - 基本動態規劃問題 - 空間復雜度可以進一步優化到 O(n), 這會是一個考點 ## 代碼 代碼支持 JavaScript,Python3 JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=62 lang=javascript * * [62] Unique Paths * * https://leetcode.com/problems/unique-paths/description/ */</span> <span class="hljs-title">/** * @param {number} m * @param {number} n * @return {number} */</span> <span class="hljs-keyword">var</span> uniquePaths = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">m, n</span>) </span>{ <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>(n).fill(<span class="hljs-params">1</span>); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i < m; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j < n; j++) { dp[j] = dp[j] + dp[j - <span class="hljs-params">1</span>]; } } <span class="hljs-keyword">return</span> dp[n - <span class="hljs-params">1</span>]; }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">uniquePaths</span><span class="hljs-params">(self, m: int, n: int)</span> -> int:</span> dp = [<span class="hljs-params">1</span>] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, m): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): dp[j] += dp[j - <span class="hljs-params">1</span>] <span class="hljs-keyword">return</span> dp[n - <span class="hljs-params">1</span>] ``` ``` **復雜度分析** - 時間復雜度: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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看