<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>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0518. 零錢兌換 II ## 題目地址(518. 零錢兌換 II) <https://leetcode-cn.com/problems/coin-change-2/> ## 題目描述 ``` <pre class="calibre18">``` 給定不同面額的硬幣和一個總金額。寫出函數來計算可以湊成總金額的硬幣組合數。假設每一種面額的硬幣有無限個。 示例 1: 輸入: amount = 5, coins = [1, 2, 5] 輸出: 4 解釋: 有四種方式可以湊成總金額: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 輸入: amount = 3, coins = [2] 輸出: 0 解釋: 只用面額 2 的硬幣不能湊成總金額 3。 示例 3: 輸入: amount = 10, coins = [10] 輸出: 1 注意: 你可以假設: 0 <= amount (總金額) <= 5000 1 <= coin (硬幣面額) <= 5000 硬幣種類不超過 500 種 結果符合 32 位符號整數 ``` ``` ## 前置知識 - [動態規劃](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) - 背包問題 ## 公司 - 阿里 - 百度 - 字節 ## 思路 這個題目和 coin-change 的思路比較類似。 我們還是按照 coin-change 的思路來, 如果將問題畫出來大概是這樣: ![](https://img.kancloud.cn/f1/1b/f11b98898dccc4675ef5b5f9219e6af4_558x433.jpg) 進一步我們可以對問題進行空間復雜度上的優化(這種寫法比較難以理解,但是相對更省空間) ![](https://img.kancloud.cn/c7/b1/c7b1841ee80cc8d58203f0b291e39229_681x394.jpg) > 這里用動圖會更好理解, 有時間的話我會做一個動圖出來, 現在大家腦補一下吧 ## 關鍵點解析 - 動態規劃 - 子問題 用 dp\[i\] 來表示組成 i 塊錢,需要最少的硬幣數,那么 1. 第 j 個硬幣我可以選擇不拿 這個時候, 組成數 = dp\[i\] 2. 第 j 個硬幣我可以選擇拿 這個時候, 組成數 = dp\[i - coins\[j\]\] + dp\[i\] 3. 和 01 背包問題不同, 硬幣是可以拿任意個,屬于完全背包問題 4. 對于每一個 dp\[i\] 我們都選擇遍歷一遍 coin, 不斷更新 dp\[i\] eg: ``` <pre class="calibre18">``` <span class="hljs-keyword">if</span> (amount === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">1</span>; <span class="hljs-keyword">const</span> dp = [<span class="hljs-params">Array</span>(amount + <span class="hljs-params">1</span>).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 < amount + <span class="hljs-params">1</span>; i++) { dp[i] = <span class="hljs-params">Array</span>(coins.length + <span class="hljs-params">1</span>).fill(<span class="hljs-params">0</span>); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j < coins.length + <span class="hljs-params">1</span>; j++) { <span class="hljs-title">// 從1開始可以簡化運算</span> <span class="hljs-keyword">if</span> (i - coins[j - <span class="hljs-params">1</span>] >= <span class="hljs-params">0</span>) { <span class="hljs-title">// 注意這里是coins[j -1]而不是coins[j]</span> dp[i][j] = dp[i][j - <span class="hljs-params">1</span>] + dp[i - coins[j - <span class="hljs-params">1</span>]][j]; <span class="hljs-title">// 由于可以重復使用硬幣所以這里是j不是j-1</span> } <span class="hljs-keyword">else</span> { dp[i][j] = dp[i][j - <span class="hljs-params">1</span>]; } } } <span class="hljs-keyword">return</span> dp[dp.length - <span class="hljs-params">1</span>][coins.length]; ``` ``` - 當我們選擇一維數組去解的時候,內外循環將會對結果造成影響 ![](https://img.kancloud.cn/58/0d/580dfac7ed75d3565f269d75be217779_684x409.jpg) eg: ``` <pre class="calibre18">``` <span class="hljs-title">// 這種答案是不對的。</span> <span class="hljs-title">// 原因在于比如amount = 5, coins = [1,2,5]</span> <span class="hljs-title">// 這種算法會將[1,2,2] [2,1,2] [2, 2, 1] 算成不同的</span> <span class="hljs-keyword">if</span> (amount === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">1</span>; <span class="hljs-keyword">const</span> dp = [<span class="hljs-params">1</span>].concat(<span class="hljs-params">Array</span>(amount).fill(<span class="hljs-params">0</span>)); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i < amount + <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">0</span>; j < coins.length; j++) { <span class="hljs-keyword">if</span> (i - coins[j] >= <span class="hljs-params">0</span>) { dp[i] = dp[i] + dp[i - coins[j]]; } } } <span class="hljs-keyword">return</span> dp[dp.length - <span class="hljs-params">1</span>]; <span class="hljs-title">// 正確的寫法應該是內外循環調換一下, 具體可以看下方代碼區</span> ``` ``` ## 代碼 代碼支持:Python3,JavaScript: JavaSCript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=518 lang=javascript * * [518] Coin Change 2 * */</span> <span class="hljs-title">/** * @param {number} amount * @param {number[]} coins * @return {number} */</span> <span class="hljs-keyword">var</span> change = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">amount, coins</span>) </span>{ <span class="hljs-keyword">if</span> (amount === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">1</span>; <span class="hljs-keyword">const</span> dp = [<span class="hljs-params">1</span>].concat(<span class="hljs-params">Array</span>(amount).fill(<span class="hljs-params">0</span>)); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">0</span>; j < coins.length; j++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i < amount + <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">if</span> (i - coins[j] >= <span class="hljs-params">0</span>) { dp[i] = dp[i] + dp[i - coins[j]]; } } } <span class="hljs-keyword">return</span> dp[dp.length - <span class="hljs-params">1</span>]; }; ``` ``` 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">change</span><span class="hljs-params">(self, amount: int, coins: List[int])</span> -> int:</span> dp = [<span class="hljs-params">0</span>] * (amount + <span class="hljs-params">1</span>) dp[<span class="hljs-params">0</span>] = <span class="hljs-params">1</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(len(coins)): <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, amount + <span class="hljs-params">1</span>): <span class="hljs-keyword">if</span> i >= coins[j]: dp[i] += dp[i - coins[j]] <span class="hljs-keyword">return</span> dp[<span class="hljs-params">-1</span>] ``` ``` **復雜度分析** - 時間復雜度:O(amount)O(amount)O(amount) - 空間復雜度:O(amount?len(coins))O(amount \* len(coins))O(amount?len(coins)) ## 擴展 這是一道很簡單描述的題目, 因此很多時候會被用到大公司的電面中。 相似問題: [322.coin-change](322.coin-change.html) ## 附錄 Python 二維解法(不推薦,但是可以幫助理解): ``` <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">change</span><span class="hljs-params">(self, amount: int, coins: List[int])</span> -> int:</span> dp = [[<span class="hljs-params">0</span> <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(len(coins) + <span class="hljs-params">1</span>)] <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(amount + <span class="hljs-params">1</span>)] <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(len(coins) + <span class="hljs-params">1</span>): dp[<span class="hljs-params">0</span>][j] = <span class="hljs-params">1</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(amount + <span class="hljs-params">1</span>): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, len(coins) + <span class="hljs-params">1</span>): <span class="hljs-keyword">if</span> i >= coins[j - <span class="hljs-params">1</span>]: dp[i][j] = dp[i - coins[j - <span class="hljs-params">1</span>]][j] + dp[i][j - <span class="hljs-params">1</span>] <span class="hljs-keyword">else</span>: dp[i][j] = dp[i][j - <span class="hljs-params">1</span>] <span class="hljs-keyword">return</span> dp[<span class="hljs-params">-1</span>][<span class="hljs-params">-1</span>] ``` ``` **復雜度分析** - 時間復雜度:O(amount?len(coins))O(amount \* len(coins))O(amount?len(coins)) - 空間復雜度:O(amount?len(coins))O(amount \* len(coins))O(amount?len(coins)) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <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>

                              哎呀哎呀视频在线观看