Blog entries - Codeforces

#	User	Rating
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

#	User	Contrib.
1	awoo	161
2	maomao90	160
3	adamant	156
4	maroonrk	153
5	-is-this-fft-	148
5	SecondThread	148
5	atcoder_official	148
8	Petr	147
9	nor	144
9	TheScrasse	144

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