Blog entries - Codeforces

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

Full text and comments »

Rainman84's blog