To brush up on my DP skills I decided to solve some problems from the topic from CSES.
I came across 2 problems of very similar solutions: Coin Combinations I and Coin Combinations II.
In the first problem, the order of the coins matter and in the second version, it does not.
What's interesting is that both these solutions are basically the same, the only difference being the order of the for loops reversed. This is where I am confused. I tried to run a few test cases by hand and managed to understand how this code works but I can't figure out why this code works the way it does.
I have a very foggy intuition about the 2nd one, wherein I am visualizing how every coin $$$c_i$$$ contributes to a particular sum (much like the sieve algorithms), But I may be wrong.
Any Help would be greatly appreciated :).
You can see that in the solution of Coin Combination II, we are always using the coins with least value first. When you were starting the j loop in that solution, we were in some way assuming that we have only one coin of value 0. Now, when we have processed for j=0 and are starting processing for j=1 we can see that it's similar to the starting of loop j=0 with only difference that we have already a coin of value 0, c[0] ,2*c[0], 3*c[0].... and we are only using one of these at a time. The whole conclusion is to give you the intuition that in the second solution all coins of similar types are always used together and coins are used in ascending order of values so it is just like sorting the values used for forming x and then calculating the number of different ways. While in first solution the last used coin can be anything. So we can have any order of the coins. Hope it was useful.
Thanks Perry_Prasad_Platypus, this has given me a better insight to the problem.
Loved this! I was confused while defining my state, how do I ensure ordering using one parameter. Amazing! Thank you rainman84 for asking this. And thank you Perry_Prasad_Platypus for explaining so well!