{"id":26018,"date":"2017-10-26T19:36:27","date_gmt":"2017-10-26T14:06:27","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26018"},"modified":"2017-10-26T19:36:27","modified_gmt":"2017-10-26T14:06:27","slug":"java-programming-coin-change","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-coin-change\/","title":{"rendered":"Java Programming &#8211; Coin Change"},"content":{"rendered":"<p>Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} 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>For example, 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<ul>\n<li><strong>Optimal Substructure<\/strong><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 mth coin (or Sm).<\/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<ul>\n<li><strong>Overlapping Subproblems<\/strong><\/li>\n<\/ul>\n<p>Following is a simple recursive implementation of the Coin Change problem. The implementation simply follows the recursive structure mentioned above.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C<\/span> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">#include&lt;stdio.h&gt;<br\/> <br\/>\/\/ Returns the count of ways we can sum  S[0...m-1] coins to get sum n<br\/>int count( int S[], int m, int n )<br\/>{<br\/>    \/\/ If n is 0 then there is 1 solution (do not include any coin)<br\/>    if (n == 0)<br\/>        return 1;<br\/>     <br\/>    \/\/ If n is less than 0 then no solution exists<br\/>    if (n &lt; 0)<br\/>        return 0;<br\/> <br\/>    \/\/ If there are no coins and n is greater than 0, then no solution exist<br\/>    if (m &lt;=0 &amp;&amp; n &gt;= 1)<br\/>        return 0;<br\/> <br\/>    \/\/ count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]<br\/>    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );<br\/>}<br\/> <br\/>\/\/ Driver program to test above function<br\/>int main()<br\/>{<br\/>    int i, j;<br\/>    int arr[] = {1, 2, 3};<br\/>    int m = sizeof(arr)\/sizeof(arr[0]);<br\/>    printf(&quot;%d &quot;, count(arr, m, 4));<br\/>    getchar();<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\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.<\/p>\n[ad type=&#8221;banner&#8221;]\nThe function C({1}, 3) 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() --&gt; 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 Overlapping Subprolems property. So the Coin Change problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array table[][] in bottom up manner.<\/p>\n<p><strong>Dynamic Programming Solution<\/strong><\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java<\/span> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/* Dynamic Programming Java implementation of Coin<br\/>   Change problem *\/<br\/>import java.util.Arrays;<br\/> <br\/>class CoinChange<br\/>{<br\/>    static long countWays(int S[], int m, int n)<br\/>    {<br\/>        \/\/Time complexity of this function: O(mn)<br\/>        \/\/Space Complexity of this function: O(n)<br\/> <br\/>        \/\/ table[i] will be storing the number of solutions<br\/>        \/\/ for value i. We need n+1 rows as the table is<br\/>        \/\/ constructed in bottom up manner using the base<br\/>        \/\/ case (n = 0)<br\/>        long[] table = new long[n+1];<br\/> <br\/>        \/\/ Initialize all table values as 0<br\/>        Arrays.fill(table, 0);   \/\/O(n)<br\/> <br\/>        \/\/ Base case (If given value is 0)<br\/>        table[0] = 1;<br\/> <br\/>        \/\/ Pick all coins one by one and update the table[]<br\/>        \/\/ values after the index greater than or equal to<br\/>        \/\/ the value of the picked coin<br\/>        for (int i=0; i&lt;m; i++)<br\/>            for (int j=S[i]; j&lt;=n; j++)<br\/>                table[j] += table[j-S[i]];<br\/> <br\/>        return table[n];<br\/>    }<br\/> <br\/>    \/\/ Driver Function to test above function<br\/>    public static void main(String args[])<br\/>    {<br\/>        int arr[] = {1, 2, 3};<br\/>        int m = arr.length;<br\/>        int n = 4;<br\/>        System.out.println(countWays(arr, m, n));<br\/>    }<br\/>}<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>4<\/pre>\n<p>Time Complexity: O(mn)<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Java Programming &#8211; Coin Change &#8211; Dynamic Programming Coin Change problem has both properties of a 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":[69969,1,83584,70145,2139],"tags":[71524,76624,76613,76611,76625,76626,76614,76610,72847,72842,72845,70483,76605,72848,72840,72846,72987,72985,72843,72854,72844,72850,72839,76607,76612,72852,72855,76606,72853,72851],"class_list":["post-26018","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-coin-change","category-dynamic-programming","category-java","tag-coin-change","tag-coin-change-in-java","tag-coin-change-problem-algorithm","tag-coin-change-problem-dynamic","tag-coin-change-problem-dynamic-programming-java","tag-coin-change-problem-in-java","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-java","tag-dynamic-programming-java","tag-dynamic-programming-problems","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\/26018","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=26018"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26018\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26018"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26018"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26018"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}