{"id":1469,"date":"2018-01-02T19:50:16","date_gmt":"2018-01-03T03:50:16","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1469"},"modified":"2018-08-01T22:44:24","modified_gmt":"2018-08-02T05:44:24","slug":"leetcode-322-coin-change","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-322-coin-change\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 322. Coin Change"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 322. Coin Change - \u5237\u9898\u627e\u5de5\u4f5c EP148\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/uUETHdijzkA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u4e0d\u540c\u5e01\u503c\u7684\u786c\u5e01\uff0c\u95ee\u4f60\u6700\u5c11\u9700\u8981\u591a\u5c11\u4e2a\u786c\u5e01\u624d\u80fd\u7ec4\u6210amount\uff0c\u5047\u8bbe\u6bcf\u79cd\u786c\u5e01\u6709\u65e0\u7a77\u591a\u4e2a\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>You are given coins of different denominations and a total amount of money\u00a0<i>amount<\/i>. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return\u00a0<code>-1<\/code>.<\/p>\n<p><b>Example 1:<\/b><br \/>\ncoins =\u00a0<code>[1, 2, 5]<\/code>, amount =\u00a0<code>11<\/code><br \/>\nreturn\u00a0<code>3<\/code>\u00a0(11 = 5 + 5 + 1)<\/p>\n<p><b>Example 2:<\/b><br \/>\ncoins =\u00a0<code>[2]<\/code>, amount =\u00a0<code>3<\/code><br \/>\nreturn\u00a0<code>-1<\/code>.<\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>DP \/knapsack<\/p>\n<p>Search<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1479 size-full\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/322-ep148.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/322-ep148.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/322-ep148-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/322-ep148-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1477\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/322-ep148-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/322-ep148-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/322-ep148-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/322-ep148-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><strong>Solution1:<\/strong><\/p>\n<p>C++ \/ DP<\/p>\n<p>Time complexity: O(n*amount^2)<\/p>\n<p>Space complexity: O(amount)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 189 ms\r\nclass Solution {\r\npublic:\r\n    int coinChange(vector&lt;int&gt;&amp; coins, int amount) {\r\n        vector&lt;int&gt; dp(amount + 1, INT_MAX);\r\n        dp[0] = 0;\r\n        for (auto coin : coins) {\r\n            for (int i = amount - coin; i &gt;= 0; --i)\r\n                if (dp[i] != INT_MAX)\r\n                    for (int k = 1; k * coin + i &lt;= amount; ++k)\r\n                        dp[i + k * coin] = min(dp[i + k * coin], dp[i] + k);\r\n        }\r\n        \r\n        return dp[amount] == INT_MAX ? -1 : dp[amount];\r\n    }\r\n};<\/pre>\n<p><strong>Solution2:<\/strong><\/p>\n<p>C++ \/ DP<\/p>\n<p>Time complexity: O(n*amount)<\/p>\n<p>Space complexity: O(amount)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 16 ms\r\nclass Solution {\r\npublic:\r\n    int coinChange(vector&lt;int&gt;&amp; coins, int amount) {\r\n        \/\/ dp[i] = min coins to make up to amount i\r\n        vector&lt;int&gt; dp(amount + 1, INT_MAX);\r\n        dp[0] = 0;\r\n        for (int coin : coins) {\r\n            for (int i = coin; i &lt;= amount; ++i)\r\n                if (dp[i - coin] != INT_MAX)  \r\n                    dp[i] = min(dp[i], dp[i - coin] + 1);\r\n        }\r\n        \r\n        return dp[amount] == INT_MAX ? -1 : dp[amount];\r\n    }\r\n};<\/pre>\n<p>Python3<\/p>\n<pre class=\"lang:default decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 632 ms beats 90.27%\r\n\"\"\"\r\nclass Solution:\r\n  def coinChange(self, coins, amount):\r\n    INVALID = 2**32\r\n    dp = [INVALID] * (amount + 1)\r\n    dp[0] = 0\r\n    for coin in coins:\r\n      for i in range(coin, amount + 1):\r\n        if dp[i - coin] &gt;= dp[i]: continue\r\n        dp[i] = dp[i - coin] + 1\r\n    return -1 if dp[amount] == INVALID else dp[amount]<\/pre>\n<p><strong>Solution3:<\/strong><\/p>\n<p>C++ \/ DFS<\/p>\n<p>Time complexity: O(amount^n\/(coin_0*coin_1*&#8230;*coin_n))<\/p>\n<p>Space complexity: O(n)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 6 ms\r\nclass Solution {\r\npublic:\r\n    int coinChange(vector&lt;int&gt;&amp; coins, int amount) {\r\n        \/\/ Sort coins in desending order\r\n        std::sort(coins.rbegin(), coins.rend());\r\n        int ans = INT_MAX;\r\n        coinChange(coins, 0, amount, 0, ans);\r\n        return ans == INT_MAX ? -1 : ans;\r\n    }\r\nprivate:\r\n    void coinChange(const vector&lt;int&gt;&amp; coins, \r\n                    int s, int amount, int count, int&amp; ans) {\r\n        if (amount == 0) {\r\n            ans = min(ans, count);\r\n            return;\r\n        }\r\n        \r\n        if (s == coins.size()) return;\r\n        \r\n        const int coin = coins[s];                \r\n        for (int k = amount \/ coin; k &gt;= 0 &amp;&amp; count + k &lt; ans; k--)\r\n            coinChange(coins, s + 1, amount - k * coin, count + k, ans);\r\n    }    \r\n};<\/pre>\n<p>Python3<\/p>\n<pre class=\"lang:default decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 200ms\r\n\"\"\"\r\nclass Solution:\r\n  def coinChange(self, coins, amount):\r\n    coins.sort(reverse=True)\r\n    INVALID = 10**10\r\n    self.ans = INVALID\r\n    def dfs(s, amount, count):      \r\n      if amount == 0:\r\n        self.ans = count\r\n        return\r\n      if s == len(coins): return\r\n      \r\n      coin = coins[s]\r\n      for k in range(amount \/\/ coin, -1, -1):\r\n        if count + k &gt;= self.ans: break\r\n        dfs(s + 1, amount - k * coin, count + k)\r\n    dfs(0, amount, 0)\r\n    return -1 if self.ans == INVALID else self.ans<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u4e0d\u540c\u5e01\u503c\u7684\u786c\u5e01\uff0c\u95ee\u4f60\u6700\u5c11\u9700\u8981\u591a\u5c11\u4e2a\u786c\u5e01\u624d\u80fd\u7ec4\u6210amount\uff0c\u5047\u8bbe\u6bcf\u79cd\u786c\u5e01\u6709\u65e0\u7a77\u591a\u4e2a\u3002 Problem: You are given coins of different denominations and a total amount of money\u00a0amount. Write a function to compute the fewest number of coins&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46,164],"tags":[18,195,177],"class_list":["post-1469","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","category-medium","tag-dp","tag-knapsack","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1469","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=1469"}],"version-history":[{"count":11,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1469\/revisions"}],"predecessor-version":[{"id":3406,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1469\/revisions\/3406"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1469"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1469"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1469"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}