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?
1
- s[n,k] either uses Kth(which is s[n-c[k-1],k]) or not (which is s[n, k-1])Herokiller– Herokiller2014-07-16 06:12:19 +00:00Commented Jul 16, 2014 at 6:12
Add a comment |
1 Answer
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.
answered Jul 16, 2014 at 9:01
Ivaylo Strandjev
71.4k18 gold badges130 silver badges183 bronze badges
1 Comment
arilato
Thanks, I didn't make the connection until I read your answer :P Brainfart