Coin Change is a pretty popular problem which asks how many ways you can get to a sum of N cents using coins (C[0], C[1]...C[K-1]). The DP solution is to use the method s(N, K) = s(N, K-1) + s(N-C[K-1], K), where s(N,K) is the amount of ways to arrive at a sum N with the first K coins(sorted in ascending order). It means the amount of ways to make N cents using the first K coins is the sum of the amount of ways to arrive at the same sum without using the Kth coin added to the amount of ways to arrive at N-the Kth coin. I really don't understand how you can come across this solution, and how it makes sense logically. Could someone explain?
The most important thing when solving a DP is to reduce the problem to a set of simpler subproblems. Most of the times "simpler" means with smaller argument(s) and in this case a problem is simpler if either the sum is less or the remaining coin values are less.
My way of thinking to solve the problem is: okay I have a set of coins and I need to count the number of ways I can form a given sum. This sounds complicated, but if I has one less coin it would be a bit easier.
It also helps to think of the bottom case. In this case you know in how many ways you can form a given sum if all you had is a single coin. This somehow suggests that the reduction to simpler problems will probably reduce the number of different coins.