title: Dynamic Coin Change Algorithm (Optimal Results)
body: <p>I have been given this part of code on Dynamic Programming (that finds the best combination of coin change. For example if we have two coins of value 3 and 4 --> {3,4};  and the amount that we want to make change is for example sum=11, the answer is that we need in total 3 coins (2 coins with value=4 and 1 coin with value=3). The code below is working good, but not exactly as I want to. <br><br>I am trying to reverse engineering the code bellow so that it will provide a more clear answer like this:</p>
  
  <pre><code>Total coins:3 , #of Coins with value "3" = 1, #of Coins with value "4" = 2
  </code></pre>
  
  <p>The number of total coins for the given amount can be found from this array minimum[sum].
      But the rest information I am trying to get (which coin is what value) , seems almost impossible to find. Also from array coins[sum][0] I can only find the last coin used , in this example its the 3 .</p>
  
  <pre><code>Inputs: sum=11 ,int[] valueCoins = new int[]{3,4}; 
  Output:
  1 10011 0(0)
  2 10011 0(0)
  3 1 3(0)
  4 1 4(0)
  5 10011 0(0)
  6 2 3(3)
  7 2 3(4)
  8 2 4(4)
  9 3 3(6)
  10 3 3(7)
  11 3 3(8)
  </code></pre>
  
  <p>As you can see it checks everything from 1 to 11,  but then it reaches 11 it stores the correct amount of coins (3) and the last coin used (3). </p>
  
  <pre class="lang-java prettyprint-override"><code>public class MinimumCoin {
  
      public static void main(String args[]){
  
          int[] valueCoins = new int[]{3,4};
          int sum = 11;
          int[] minimum = new int[sum+1];
          int[][] coins = new int[sum+1][2];
  
          /* initializing the minimum of every sum to infinity */
          for(int i = 1; i &lt; minimum.length; i++){
              minimum[i] = sum + 10000;
          }
          /* initializing that for minumum sum of zero, 0 coin is required */
          minimum[0] = 0;
  
          for(int i = 1; i &lt;= sum; i++){
              for(int j = 0; j &lt;valueCoins.length; j++){
                  if(valueCoins[j] == i){
                      minimum[i] = 1;
                      coins[i][0] = i;
                      coins[i][1] = 0;
                  }
                  else if((valueCoins[j] &lt; i) &amp;&amp; (((minimum[i-valueCoins[j]]) + 1) &lt; minimum[i])){
  
                      minimum[i] = (minimum[i-valueCoins[j]]) + 1;
                      coins[i][0] = valueCoins[j];
                      coins[i][1] = (i-valueCoins[j]);
                  }
              }
          }
  
          for(int k = 1; k &lt; minimum.length; k++){
              System.out.println( k + " " + minimum[k] + " " + coins[k][0] +"("+ coins[k][1] +")");
          }
      }
  }
  </code></pre>
  
  <p>Thanks for any input! </p>
  
  <p>~Regards, S</p>