title: Dynamic programming - Coin change decision
body: <p>I'm reviewing some old notes from my algorithms course and the dynamic programming problems are seeming a bit tricky to me.  I have a problem where we have an unlimited supply of coins, with some denominations x1, x2, ... xn and we want to make change for some value X.  We are trying to design a dynamic program to decide whether change for X can be made or not (not minimizing the number of coins, or returning which coins, just true or false).</p>
  
  <p>I've done some thinking about this problem, and I can see a recursive method of doing this where it's something like...</p>
  
  <pre><code>MakeChange(X, x[1..n this is the coins])
      for (int i = 1; i &lt; n; i++)
      {
          if ( (X - x[i] ==0) || MakeChange(X - x[i]) )
              return true;
      }
      return false;
  </code></pre>
  
  <p>Converting this a dynamic program is not coming so easily to me.  How might I approach this?</p>