title: Dynamic Programming - making change
body: <p>I'm having trouble figuring out my last section of code for a Dynamic Coin Changing Problem. I have included the code below.</p>
  
  <p>I can't figure out the last <code>else</code>. Should I just use the greedy algorithm at that point or can I calculate the answer from values already in the table? I've worked hard on trying to understand this problem and I think I'm pretty close. The method finds the minimum amount of coins needed to make a certain amout of change by creating a table and using the results that are stored in the table to solve the larger problem without using recursion.</p>
  
  <pre><code>public static int minCoins(int[] denom, int targetAmount){
      int denomPosition; // Position in denom[] where the first spot
                         // is the largest coin and includes every coin
                         // smaller.
      int currentAmount; // The Amount of money that needs to be made
                         // remainingAmount &lt;= initalAmount
      int[][] table = new int[denom.length][targetAmount+1];
      for(denomPosition = denom.length-1 ; denomPosition &gt;= 0 ; denomPosition--) {
          for(currentAmount = 0 ; currentAmount &lt;= targetAmount ; currentAmount++){
              if (denomPosition == denom.length-1){
                  table[denomPosition][currentAmount] = 
                       currentAmount/denom[denomPosition];
              }
              else if (currentAmount&lt;denom[denomPosition]){
                  table[denomPosition][currentAmount] = 
                       table[denomPosition+1][currentAmount];
              }
              else{           
                  table[denomPosition][currentAmount] = 
                       table[denomPosition+1][currentAmount]-
                       table[denomPosition][denom[denomPosition]]-1;
              }
          }
      }
      return table[0][targetAmount];
  }
  </code></pre>