title: What is the difference between approaches to "coin change" and "Number of of ways of climbing staircase"
body: <p>I have come across two dynamic programming problems. One of the problems is </p>
  
  <p><strong>What is the number of possible ways to climb a staircase with n steps given that I can hop either 1 , 2 or 3 steps at a time.</strong></p>
  
  <p>The Dynamic programming approach for solving this problem goes as follows.</p>
  
  <pre><code>If C(n) is number of ways of climbing the staircase, then 
  C(n) = C(n-1) + C(n-2) + C(n-3) . 
  This is because , if we reach n-1 stairs, we can hop to n by 1 step hop or
                    if we reach n-2 stairs, we can hop to n by 2 step hop or
                    if we reach n-3 stairs, we can hop to n by 3 step hop
  </code></pre>
  
  <p>As I was about to think, I understood the above approach, I came across the coin change problem which is</p>
  
  <p><strong>What is the number of ways of representing n cents, given infinite number of 25 cent coins, 10 cent coins (dimes), 5 cent coins(nickels) and 1 cent coins</strong></p>
  
  <p>It turns out the solution for this problem is not similar to the one above and is bit complex. That is ,
  <strong>C(n) = C(n-1) + C(n-5) + C(n-10) + C(n-25) is not true</strong>. I am still trying to understand the approach for solving this problem. But my question is <strong>How is the coin change problem different from the much simpler climbing steps problem?</strong></p>