{"id":949,"date":"2021-03-12T00:12:42","date_gmt":"2021-03-11T16:12:42","guid":{"rendered":"http:\/\/lonelinerd.com\/?p=949"},"modified":"2021-03-12T12:02:57","modified_gmt":"2021-03-12T04:02:57","slug":"leetcode-322","status":"publish","type":"post","link":"https:\/\/lonelinerd.com\/index.php\/2021\/03\/12\/leetcode-322\/","title":{"rendered":"[LeetCode\u5237\u984c\u7b46\u8a18] 322 – Coin Change"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t

\u984c\u76ee\u63cf\u8ff0\uff1a<\/strong><\/span><\/h4>

You are given coins of different denominations and a total amount of money <\/span>amount<\/span><\/em><\/span>. 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 <\/span>-1<\/code><\/span>.<\/span><\/p>

You may assume that you have an infinite number of each kind of coin.<\/span><\/p>

\u00a0<\/p>

Example 1:<\/span><\/strong><\/span><\/p>

Input: coins = [1,2,5], amount = 11<\/span>
Output: 3<\/span>
Explanation: 11 = 5 + 5 + 1<\/span><\/pre>
Example 2:<\/span><\/strong><\/span><\/p>
Input: coins = [2], amount = 3<\/span>
Output: -1<\/span><\/pre>
Example 3:<\/span><\/strong><\/span><\/p>
Input: coins = [1], amount = 0<\/span>
Output: 0<\/span><\/pre>
Example 4:<\/span><\/strong><\/span><\/p>
Input: coins = [1], amount = 1<\/span>
Output: 1<\/span><\/pre>
Example 5:<\/span><\/strong><\/span><\/p>
Input: coins = [1], amount = 2<\/span>
Output: 2<\/span><\/pre>
\u00a0<\/p>
Constraints:<\/span><\/strong><\/span><\/p>
  • 1 <= coins.length <= 12<\/code><\/span><\/p><\/li>
  • 1 <= coins[i] <= 231 - 1<\/code><\/span><\/p><\/li>
  • 0 <= amount <= 104<\/code><\/span><\/p><\/li><\/ul>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t
    \n\t\t\t\t
    \u4e00\u5237\u984c\u89e3\uff08Dynamic Programming\uff09\uff1a<\/strong><\/span><\/h4>
    \u00a0 \u00a0 \u00a0 \u00a0 \u9019\u984c\u7d66\u4e86\u6211\u5011\u4e00\u500b\u300c\u786c\u5e63\u5e63\u503c\u300d\u7684\u6578\u7d44\u9084\u6709\u4e00\u500b\u76ee\u6a19\u91d1\u984d\uff0c\u9700\u8981\u6211\u5011\u7d44\u5408\u9019\u4e9b\u786c\u5e63\uff08\u6bcf\u679a\u786c\u5e63\u90fd\u53ef\u91cd\u8907\u4f7f\u7528\uff09\uff0c\u4f7f\u786c\u5e63\u7e3d\u503c\u7b49\u540c\u76ee\u6a19\u91d1\u984d\uff0c\u6bcf\u4f7f\u7528\u4e00\u500b\u786c\u5e63\uff0c\u4f7f\u7528\u6b21\u6578+1\uff0c\u6700\u5f8c\u8981\u8fd4\u56de\u6700\u4f4e\u7684\u53ef\u80fd\u4f7f\u7528\u6b21\u6578\uff0c\u5982\u679c\u5be6\u5728\u662f\u7121\u6cd5\u6e4a\u9f4a\u5c31\u8fd4\u56de-1\u3002\u9019\u984c\u770b\u4e0a\u53bb\u601d\u8def\u5f88\u7c21\u55ae\uff0c\u4f46\u505a\u8d77\u4f86\u9084\u662f\u6709\u4e00\u9ede\u9ebb\u7169\u7684\u3002<\/p>
    \u00a0 \u00a0 \u00a0 \u00a0 \u6211\u5c0d\u9019\u984c\u7684\u7b2c\u4e00\u53cd\u61c9\u662f\u4f7f\u7528\u8caa\u5fc3\u7b97\u6cd5\u4f86\u505a\uff0c\u5148\u628a\u786c\u5e63\u6578\u7d44\u9032\u884c\u6392\u5e8f\uff0c\u7136\u5f8c\u53cd\u8986\u5c07\u76ee\u6a19\u91d1\u984d\u6e1b\u53bb\u6578\u7d44\u5c3e\u90e8\u5143\u7d20\uff08\u6700\u9ad8\u5e63\u503c\uff09\uff0c\u7576\u5143\u7d20>\u76ee\u6a19\u91d1\u984d\uff0c\u5247\u4e0b\u6a19\u5411\u524d\u3002\u4f46\u662f\u9019\u4e00\u984c\u4e26\u4e0d\u80fd\u9019\u9ebc\u505a\uff0c\u56e0\u70ba\u9019\u984c\u7684\u76ee\u6a19\u662f\u300c\u8981\u4e0d\u591a\u4e0d\u5c11\u5730\u300d\u6e4a\u9f4a\u76ee\u6a19\u91d1\u984d\uff0c\u4e5f\u5c31\u662f\u8aaa\uff0c\u6700\u5feb\u6e4a\u9f4a\u76ee\u6a19\u91d1\u984d\u7684\u7d44\u5408\u6709\u53ef\u80fd\u4e0d\u5305\u542b\u6700\u9ad8\u5e63\u503c\u7684\u786c\u5e63\u3002\u9019\u6a23\u4e00\u4f86\uff0c\u9019\u984c\u5c31\u7121\u6cd5\u4f7f\u7528\u8caa\u5fc3\u7b97\u6cd5\u4e86\u3002<\/p>
    \u00a0 \u00a0 \u00a0 \u00a0 \u53d6\u800c\u4ee3\u4e4b\uff0c\u6211\u8166\u6d77\u88e1\u6e67\u73fe\u51fa\u4f86\u7684\u5c31\u662fDFS\uff0c\u5c0d\u4f7f\u7528\u6bcf\u500b\u786c\u5e63\u7684\u53ef\u80fd\u6027\u9032\u884c\u905e\u6b78\u3002\u6bcf\u4f7f\u7528\u4e00\u6b21\u786c\u5e63\uff0c\u5c31\u589e\u52a0\u4e00\u6b21\u6b65\u6578\u4e26\u628a\u76ee\u6a19\u91d1\u984d\u6e1b\u53bb\u4f7f\u7528\u786c\u5e63\u7684\u5e63\u503c\uff0c\u7136\u5f8c\u5c07\u9019\u500b\u76ee\u6a19\u91d1\u984d\u5411\u4e0b\u50b3\uff0c\u91cd\u8907\u6aa2\u67e5\uff0c\u76f4\u5230\u5e63\u503c = 0 \u6216\u8005 \u6700\u5c0f\u7684\u5e63\u503c\u5927\u65bc\u76ee\u6a19\u91d1\u984d\u70ba\u6b62\u3002\u7576\u7136\u6bcf\u7576\u4e00\u500b\u53ef\u80fd\u6027\u628a\u6b65\u6578\u8fd4\u56de\u5230\u4e0a\u4e00\u5c64\u6642\uff0c\u4e0a\u4e00\u5c64\u90fd\u8981\u5224\u65b7\u9019\u500b\u503c\u662f\u4e0d\u662f\u9019\u9ebc\u591a\u7a2e\u53ef\u80fd\u6027\u4e2d\u7684\u6700\u5c0f\u503c\u3002\uff08if(stepCnt >= 0 && stepCnt < minValue) { minValue = stepCnt + 1; })<\/p>
    \u00a0 \u00a0 \u00a0 \u00a0 \u6700\u5f8c\uff0c\u628a\u9019\u500b\u7d50\u679c\u8a18\u9304\u5230\u4f5c\u70ba\u5b58\u5132\u7d50\u679c\u6578\u7d44\u7684\u5c0d\u61c9\u7d22\u5f15\u4e0a\uff0c\u5f9e\u800c\u7701\u53bb\u4e4b\u5f8c\u9047\u5230\u91cd\u8907\u554f\u984c\u6642\u7684\u8a08\u7b97\u6642\u9593\uff0c\u9019\u4e5f\u662fDynamic Programming\u7684\u6838\u5fc3\u3002<\/p>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t
    \n\t\t\t\t
    public<\/span> class<\/span> Solution<\/span> {<\/span>
     \u00a0 \u00a0public<\/span> int<\/span> CoinChange<\/span>(int<\/span>[] coins<\/span>, int<\/span> amount<\/span>)<\/span>
     \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0if<\/span> (amount<\/span> ==<\/span> 0<\/span>) { return<\/span> 0<\/span>; }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0Array<\/span>.Sort<\/span>(coins<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0int<\/span>[] memo<\/span> =<\/span> new<\/span> int<\/span>[amount<\/span>];<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0return<\/span> ClearCoinPathCounter<\/span>(coins<\/span>, amount<\/span>, memo<\/span>);<\/span>
     \u00a0  }<\/span>
     \u00a0 \u00a0int<\/span> ClearCoinPathCounter<\/span>(int<\/span>[] coins<\/span>, int<\/span> amount<\/span>, int<\/span>[] memo<\/span>)<\/span>
     \u00a0  {
    <\/span>        \/\/\u7576\u76ee\u6a19\u91d1\u984d=0\uff0c\u627e\u5230\u4e00\u7a2e\u984c\u89e3
     \u00a0 \u00a0 \u00a0 \u00a0if<\/span> (amount<\/span> ==<\/span> 0<\/span>) { return<\/span> 0<\/span>; }<\/span>
            \/\/\u5617\u8a66\u5f9e\u5b58\u5132\u7d50\u679c\u6578\u7d44\u4e2d\u63d0\u53d6\u7d50\u679c\uff0c\u7701\u53bb\u4e0b\u9762\u7684\u8a08\u7b97\u6b65\u9a5f
     \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(memo<\/span>[amount<\/span> -<\/span> 1<\/span>] !=<\/span> 0<\/span>) { return<\/span> memo<\/span>[amount<\/span> -<\/span> 1<\/span>]; }<\/span>

     \u00a0 \u00a0 \u00a0 \u00a0int<\/span> minValue<\/span> =<\/span> int<\/span>.MaxValue<\/span>;
    <\/span>        \/\/\u904d\u6b77\u786c\u5e63\u6578\u7d44\u7684\u6bcf\u500b\u5143\u7d20\uff0c\u9032\u884c\u905e\u6b78\u6aa2\u67e5\u7576\u524d\u76ee\u6a19\u91d1\u984d\u4e0b\u6240\u6709\u53ef\u80fd\u6027
     \u00a0 \u00a0 \u00a0 \u00a0for<\/span> (int<\/span> i<\/span> =<\/span> 0<\/span>; i<\/span> <<\/span> coins<\/span>.Length<\/span>; i<\/span>++<\/span>)<\/span>
     \u00a0 \u00a0 \u00a0  {
    <\/span>            \/\/\u7531\u65bc\u786c\u5e63\u6578\u503c\u662f\u6700\u5c0f\u5230\u5927\u9806\u5e8f\u6392\u5e8f\u7684\uff0c\u5982\u679c\u67d0\u500b\u786c\u5e63\u5e63\u503c>\u76ee\u6a19\u91d1\u984d\uff0c\u5176\u5f8c\u7684\u786c\u5e63\u5e63\u503c\u4e5f\u4e00\u5b9a>\u76ee\u6a19\u91d1\u984d
                \/\/\u800c\u984c\u76ee\u8981\u6c42\u6211\u5011\u8fd4\u56de\u4e00\u500b\u300c\u525b\u597d\u6e4a\u9f4a\u76ee\u6a19\u91d1\u984d\u300d\uff08amount == 0\uff09\u7684\u65b9\u6848\uff0c
                \/\/\u56e0\u6b64\u7576\u786c\u5e63\u5e63\u503c>\u76ee\u6a19\u91d1\u984d\u6642\uff0c\u4ee3\u8868\u9078\u64c7\u8a72\u786c\u5e63\u7121\u6cd5\u9054\u6210\u76ee\u6a19\uff0c\u53ef\u4ee5\u76f4\u63a5\u4e2d\u65b7\u5faa\u74b0
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(amount<\/span> <<\/span> coins<\/span>[i<\/span>]) { break<\/span>; }
    <\/span>            \/\/\u5411\u4e0b\u905e\u6b78\uff0c\u5f97\u5230\u8a72\u53ef\u80fd\u6027\u4e0b\u9054\u5230\u76ee\u6a19\u7684\u6b65\u6578
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0int<\/span> stepCnt<\/span> =<\/span> ClearCoinPathCounter<\/span>(coins<\/span>, amount<\/span> -<\/span> coins<\/span>[i<\/span>], memo<\/span>);
    <\/span>            \/\/\u78ba\u5b9a\u8fd4\u56de\u7576\u524d\u5c64\u7684\u6b65\u6578\u4e0d\u662f-1\uff08\u7121\u6cd5\u9054\u5230\u76ee\u6a19\uff09\u4ee5\u53ca\u5c0f\u65bc\u7576\u524d\u6700\u5c0f\u503c
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(stepCnt<\/span> >=<\/span> 0<\/span> &&<\/span> stepCnt<\/span> <<\/span> minValue<\/span>)<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {
    <\/span>                \/\/\u6b65\u6578 + 1
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0minValue<\/span> =<\/span> stepCnt<\/span> +<\/span> 1<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0  }<\/span>
            \/\/\u8a18\u9304\u7d50\u679c\u5230\u5b58\u5132\u7d50\u679c\u7684\u6578\u7d44\u88e1
     \u00a0 \u00a0 \u00a0 \u00a0memo<\/span>[amount<\/span> -<\/span> 1<\/span>] =<\/span> minValue<\/span> ==<\/span> int<\/span>.MaxValue<\/span> ?<\/span> -<\/span>1<\/span> : minValue<\/span>;
    <\/span>        \/\/\u8fd4\u56de\u7576\u524d\u5c64\u7d50\u679c
     \u00a0 \u00a0 \u00a0 \u00a0return<\/span> memo<\/span>[amount<\/span> -<\/span> 1<\/span>];<\/span>
     \u00a0  }<\/span>
    }<\/span><\/pre>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t
    \u601d\u8def\u5716\uff1a<\/h2>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"
    \u984c\u76ee\u63cf\u8ff0\uff1a You are given coins of different denominations an …<\/p>\n
      [LeetCode\u5237\u984c\u7b46\u8a18] 322 – Coin Change<\/span> Read More »<\/a><\/p>\n","protected":false},"author":1,"featured_media":570,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,16],"tags":[],"class_list":["post-949","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming-notes","category-leetcodes"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/lonelinerd.com\/wp-content\/uploads\/2021\/02\/FeatureCover_LeetCoding.png","_links":{"self":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/949","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/comments?post=949"}],"version-history":[{"count":17,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/949\/revisions"}],"predecessor-version":[{"id":969,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/949\/revisions\/969"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media\/570"}],"wp:attachment":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media?parent=949"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/categories?post=949"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/tags?post=949"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}