I have come across two dynamic programming problems. One of the problems is
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.
The Dynamic programming approach for solving this problem goes as follows.
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
As I was about to think, I understood the above approach, I came across the coin change problem which is
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
It turns out the solution for this problem is not similar to the one above and is bit complex. That is , C(n) = C(n-1) + C(n-5) + C(n-10) + C(n-25) is not true. I am still trying to understand the approach for solving this problem. But my question is How is the coin change problem different from the much simpler climbing steps problem?