What is the difference between approaches to "coin change" and "Number of of ways of climbing staircase"

Question

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?

Answer 1

In the steps problem, the order matters: (1,2) is not the same as (2,1). With the coin problem, only the number of each type of coin used matters.

Answer 2

Scott's solution is absolutely correct, and he mentions the crux of the difference between the two problems. Here's a little more color on the two problems to help intuitively understand the difference.

For Dynamic Programming problems that involve recursion, the trick is to get the subproblem right. Once the subproblem is correct, it is just a matter of building on top of that.

The Staircase problem deals with sequences so the subproblem is easier to see intuitively. For the Coin-change problem, we are dealing with counts so the subproblem is around whether or not to use a particular denomination. We compute one part of the solution using a denomination, and another without using it. That is a slightly more difficult insight to see, but once you see that, you can recursively compute the rest.

So here's one way to think about the two problems:

Staircase Sequence

Introduce one new step. The nth step has been added. How do we compute S[N]?

S[N] = S[N-1] + S[N-2] + S[N-3]

Coin Change

Introduce a new small coin denomination. Let's say a coin of denomination 'm' has newly been introduced. How do we now compute C[n], knowing C[N, with all coins except m]?

All the ways to reach N without coin m still hold. But each new coin denomination 'm' fundamentally changes the ways to get to N. So to compute C[N using m] we have to recursively compute C[N-m, using the new coin m], and C[N-2m using m]...and so on.

C[N, with m] = C[N, without m] + C[N-m, with m]

Hope that helps.