[HELP NEEDED] Why does these solutions for CSES Coin Combination 1 & 2 work ?

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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.

Code for 1st problem

{
    int n, x;
    cin >> n >> x;
    vector<int> c(n);
    forn(i, n)
    {
        cin >> c[i];
    }
    sort(all(c));
    vector<int> dp(x + 1, 0);
    dp[0] = 1;
    for (int j = 0; j <= x; j++)
    {
        for (int i = 0; i < n && c[i] <= j; i++)
        {
            dp[j] += dp[j - c[i]];
            dp[j] %= MOD;
        }
    }
    cout << dp[x] << "\n";
}

Code for 2nd Problem

void solve()
{
    int n, x;
    cin >> n >> x;
    vector<int> c(n);
    forn(i, n)
    {
        cin >> c[i];
    }
    sort(all(c));
    vector<int> dp(x + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= x; j++)
        {
            if (c[i] <= j)
            {
                dp[j] += dp[j - c[i]];
                dp[j] %= MOD;
            }
        }
    }
    cout << dp[x] << "\n";
}

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 :).

Comments (3)

Show archived | Write comment?

Perry_Prasad_Platypus

4 years ago, # |

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.

→ Reply

Rainman84

4 years ago, # ^ |

Thanks Perry_Prasad_Platypus, this has given me a better insight to the problem.

saketbyte

11 days ago, # |

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!

Rainman84's blog