{"id":26019,"date":"2017-10-26T09:51:30","date_gmt":"2017-10-26T04:21:30","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26019"},"modified":"2018-10-31T14:24:08","modified_gmt":"2018-10-31T08:54:08","slug":"python-programming-coin-change","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-coin-change\/","title":{"rendered":"Coin Change Problem"},"content":{"rendered":"<p><strong><span style=\"color: #003300;\">Coin Change Problem<\/span><\/strong><\/p>\n<p>Given a value N, if we want to make change for <strong>N cents<\/strong>, and we have infinite supply of each of <strong>S = { S1, S2, .. , Sm}<\/strong> valued coins, how many ways can we make the change? The order of coins doesn\u2019t matter.<span id=\"more-17401\"><\/span><\/p>\n<p><span style=\"color: #008080;\"><strong>For example<\/strong><\/span>, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter  wp-image-31779\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/coin-change-problem.png\" alt=\"coin change problem\" width=\"425\" height=\"237\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/coin-change-problem.png 1297w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/coin-change-problem-300x168.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/coin-change-problem-768x428.png 768w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/coin-change-problem-1024x571.png 1024w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/coin-change-problem-215x120.png 215w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/coin-change-problem-414x232.png 414w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/coin-change-problem-990x552.png 990w\" sizes=\"(max-width: 425px) 100vw, 425px\" \/><\/p>\n<ul>\n<li><span style=\"color: #008000;\"><strong>Optimal Substructure<\/strong><\/span><br \/>\nTo count total number solutions, we can divide all set solutions in two sets.<\/p>\n<ul>\n<li>Solutions that do not contain <strong>mth<\/strong> coin (or <strong>Sm<\/strong>).<\/li>\n<li>Solutions that contain at least one Sm.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).<\/p>\n<p>Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems.<\/p>\n[ad type=\u201dbanner\u201d]\n<ul>\n<li><span style=\"color: #008000;\"><strong>Overlapping Subproblems<\/strong><\/span><\/li>\n<\/ul>\n<p>Following is a simple recursive implementation of the <a href=\"https:\/\/www.wikitechy.com\/technology\/c-programming-coin-change\/\" target=\"_blank\" rel=\"noopener\">Coin Change problem<\/a>. The implementation simply follows the recursive structure mentioned above using <a href=\"https:\/\/www.wikitechy.com\/tutorials\/python\/python-program-to-find-area-of-a-triangle\" target=\"_blank\" rel=\"noopener\">Python code.<\/a><\/p>\n<h3 id=\"implementation-of-coin-change-using-python\"><span style=\"color: #003366;\">Implementation of Coin change using Python:<\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%0A%23%20Recursive%20Python3%20program%20for%20%0A%23%20coin%20change%20problem.%20%0A%20%20%0A%23%20Returns%20the%20count%20of%20ways%20we%20can%20sum%20%0A%23%20S%5B0\u2026m-1%5D%20coins%20to%20get%20sum%20n%20%0Adef%20count(S%2C%20m%2C%20n%20)%3A%20%0A%20%20%0A%20%20%20%20%23%20If%20n%20is%200%20then%20there%20is%201%20%0A%20%20%20%20%23%20solution%20(do%20not%20include%20any%20coin)%20%0A%20%20%20%20if%20(n%20%3D%3D%200)%3A%20%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%0A%20%20%20%20%23%20If%20n%20is%20less%20than%200%20then%20no%20%0A%20%20%20%20%23%20solution%20exists%20%0A%20%20%20%20if%20(n%20%3C%200)%3A%20%0A%20%20%20%20%20%20%20%20return%200%3B%20%0A%20%20%0A%20%20%20%20%23%20If%20there%20are%20no%20coins%20and%20n%20%0A%20%20%20%20%23%20is%20greater%20than%200%2C%20then%20no%20%0A%20%20%20%20%23%20solution%20exist%20%0A%20%20%20%20if%20(m%20%3C%3D0%20and%20n%20%3E%3D%201)%3A%20%0A%20%20%20%20%20%20%20%20return%200%0A%20%20%0A%20%20%20%20%23%20count%20is%20sum%20of%20solutions%20(i)%20%20%0A%20%20%20%20%23%20including%20S%5Bm-1%5D%20(ii)%20excluding%20S%5Bm-1%5D%20%0A%20%20%20%20return%20count(%20S%2C%20m%20-%201%2C%20n%20)%20%2B%20count(%20S%2C%20m%2C%20n-S%5Bm-1%5D%20)%3B%20%0A%20%20%0A%23%20Driver%20program%20to%20test%20above%20function%20%0Aarr%20%3D%20%5B1%2C%202%2C%203%5D%20%0Am%20%3D%20len(arr)%20%0Aprint(count(arr%2C%20m%2C%204))%20\u2033 message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for S = {1, 2, 3} and n = 5.<br \/>\nThe function<strong> C({1}, 3)<\/strong> is called two times. If we draw the complete tree, then we can see that there are many subproblems being called more than once.<\/p>\n<pre>C() --> count()\r\n                              C({1,2,3}, 5)                     \r\n                           \/                \\\r\n                         \/                   \\              \r\n             C({1,2,3}, 2)                 C({1,2}, 5)\r\n            \/     \\                        \/         \\\r\n           \/        \\                     \/           \\\r\nC({1,2,3}, -1)  C({1,2}, 2)        C({1,2}, 3)    C({1}, 5)\r\n               \/     \\            \/    \\            \/     \\\r\n             \/        \\          \/      \\          \/       \\\r\n    C({1,2},0)  C({1},2)   C({1,2},1) C({1},3)    C({1}, 4)  C({}, 5)\r\n                   \/ \\      \/ \\       \/ \\        \/     \\    \r\n                  \/   \\    \/   \\     \/   \\      \/       \\ \r\n                .      .  .     .   .     .   C({1}, 3) C({}, 4)\r\n                                               \/  \\\r\n                                              \/    \\  \r\n                                             .      .\r\n<\/pre>\n<p>Since same suproblems are called again, this problem has <a href=\"https:\/\/www.wikitechy.com\/technology\/python-programming-overlapping-subproblems-property\/\" target=\"_blank\" rel=\"noopener\">Overlapping Subproblems property<\/a>. So the Coin Change problem has both properties of a dynamic programming problem. Like other typical <a href=\"https:\/\/www.wikitechy.com\/technology\/box-stacking-problem\/\" target=\"_blank\" rel=\"noopener\">Dynamic Programming<\/a>(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array table[][] in bottom up manner.<\/p>\n[ad type=\u201dbanner\u201d]\n<h3 id=\"dynamic-programming-solution\"><span style=\"color: #993300;\"><strong>Dynamic Programming Solution<\/strong><\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Dynamic%20Programming%20Python%20implementation%20of%20Coin%20Change%20problem%0Adef%20count(S%2C%20m%2C%20n)%3A%0A%20%20%20%20%23%20We%20need%20n%2B1%20rows%20as%20the%20table%20is%20consturcted%20in%20bottom%20up%0A%20%20%20%20%23%20manner%20using%20the%20base%20case%200%20value%20case%20(n%20%3D%200)%0A%20%20%20%20table%20%3D%20%5B%5B0%20for%20x%20in%20range(m)%5D%20for%20x%20in%20range(n%2B1)%5D%0A%20%0A%20%20%20%20%23%20Fill%20the%20enteries%20for%200%20value%20case%20(n%20%3D%200)%0A%20%20%20%20for%20i%20in%20range(m)%3A%0A%20%20%20%20%20%20%20%20table%5B0%5D%5Bi%5D%20%3D%201%0A%20%0A%20%20%20%20%23%20Fill%20rest%20of%20the%20table%20enteries%20in%20bottom%20up%20manner%0A%20%20%20%20for%20i%20in%20range(1%2C%20n%2B1)%3A%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(m)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Count%20of%20solutions%20including%20S%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20x%20%3D%20table%5Bi%20-%20S%5Bj%5D%5D%5Bj%5D%20if%20i-S%5Bj%5D%20%3E%3D%200%20else%200%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Count%20of%20solutions%20excluding%20S%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20y%20%3D%20table%5Bi%5D%5Bj-1%5D%20if%20j%20%3E%3D%201%20else%200%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20total%20count%0A%20%20%20%20%20%20%20%20%20%20%20%20table%5Bi%5D%5Bj%5D%20%3D%20x%20%2B%20y%0A%20%0A%20%20%20%20return%20table%5Bn%5D%5Bm-1%5D%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aarr%20%3D%20%5B1%2C%202%2C%203%5D%0Am%20%3D%20len(arr)%0An%20%3D%204%0Aprint(count(arr%2C%20m%2C%20n))%0A%20\u2033 message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #003300;\">Output:<\/span><\/h3>\n<pre>4<\/pre>\n<p><strong><span style=\"color: #0000ff;\">Time Complexity:<\/span> O(mn)<\/strong><\/p>\n<p>Following is a simplified version of method 2. The auxiliary space required here is <strong>O(n)<\/strong> only.<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Dynamic%20Programming%20Python%20implementation%20of%20Coin%20%0A%23%20Change%20problem%0Adef%20count(S%2C%20m%2C%20n)%3A%0A%20%0A%20%20%20%20%23%20table%5Bi%5D%20will%20be%20storing%20the%20number%20of%20solutions%20for%0A%20%20%20%20%23%20value%20i.%20We%20need%20n%2B1%20rows%20as%20the%20table%20is%20constructed%0A%20%20%20%20%23%20in%20bottom%20up%20manner%20using%20the%20base%20case%20(n%20%3D%200)%0A%20%20%20%20%23%20Initialize%20all%20table%20values%20as%200%0A%20%20%20%20table%20%3D%20%5B0%20for%20k%20in%20range(n%2B1)%5D%0A%20%0A%20%20%20%20%23%20Base%20case%20(If%20given%20value%20is%200)%0A%20%20%20%20table%5B0%5D%20%3D%201%0A%20%0A%20%20%20%20%23%20Pick%20all%20coins%20one%20by%20one%20and%20update%20the%20table%5B%5D%20values%0A%20%20%20%20%23%20after%20the%20index%20greater%20than%20or%20equal%20to%20the%20value%20of%20the%0A%20%20%20%20%23%20picked%20coin%0A%20%20%20%20for%20i%20in%20range(0%2Cm)%3A%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(S%5Bi%5D%2Cn%2B1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20table%5Bj%5D%20%2B%3D%20table%5Bj-S%5Bi%5D%5D%0A%20%0A%20%20%20%20return%20table%5Bn%5D%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aarr%20%3D%20%5B1%2C%202%2C%203%5D%0Am%20%3D%20len(arr)%0An%20%3D%204%0Ax%20%3D%20count(arr%2C%20m%2C%20n)%0Aprint%20(x)%0A%20\u2033 message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output-2\"><span style=\"color: #003300;\">Output:<\/span><\/h3>\n<pre>4<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Python Programming &#8211; Coin Change &#8211; Dynamic Programming Coin Change problem has both properties of dynamic programming problem. Like other typical DP problem<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,83584,70145,4148],"tags":[71524,76627,76613,76611,76628,76629,76614,76610,72847,72842,72845,70483,76605,72848,72840,72846,72994,72843,72992,72854,72844,72850,72839,76607,76612,72852,72855,76606,72853,72851],"class_list":["post-26019","post","type-post","status-publish","format-standard","hentry","category-coding","category-coin-change","category-dynamic-programming","category-python","tag-coin-change","tag-coin-change-in-python","tag-coin-change-problem-algorithm","tag-coin-change-problem-dynamic","tag-coin-change-problem-dynamic-programming-python","tag-coin-change-problem-in-python","tag-coin-change-problem-number-of-ways","tag-coin-change-problem-recursive-solution","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-and-coin-change","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-python","tag-dynamic-programming-problems","tag-dynamic-programming-python","tag-dynamic-programming-set-1","tag-dynamic-programming-software","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-minimum-coin-change-problem-dynamic-programming","tag-number-of-ways-to-make-change","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-the-coin-change-problem","tag-types-of-dynamic-programming","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26019","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26019"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26019\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26019"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26019"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26019"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}