Rakim's Notes

Coin Combination II

3 min read

CSES Problem Link: https://cses.fi/problemset/result/14566882/

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.
For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

2+2+5
3+3+3
2+2+2+3

So in this problem, we would need the coins to be taken in a specific order, i.e after moving to 3, we can’t go back to 2 since we would have duplicate counts:
{2,3} -> {3,2} in this problem.

If we didn’t need to care about the order then what we could’ve done is the following:

where n is the number of Coins

But since we are required to take the elements in a specific order, we would need one additional parameter for each state to be unique: Either we can store the last element we chose or keep track of the last index

I am choosing to go with keeping track of index as it can at max be 100 whereas elements can have size up to 1e5.

So our new state would be F(x, i) which would be the number of ways we can achieve sum x by choosing elements in range [i, N-1]

Transition:

But that is quite troublesome to tabulate so we could also state it in the following way:

It would have the base case of if i+1 == n, then return 0
(try working it out with a small example and convince yourself both are equivalent expression)

So the problem boils down to a take or no take!
In case we skip the current state then we move to i+1 otherwise we will subtract Coin_i and stay at i

  dp[0][0] = 1;
  for (int j = 0; j <= x; j++) {
    for (int i = 0; i < n; i++) {
      if (i - 1 >= 0)
        dp[i][j] = dp[i - 1][j];
      if (j - coins[i] >= 0)
        dp[i][j] = (dp[i][j] + dp[i][j - coins[i]]) % mod;
    }
  }

This would still TLE on CSES so we need to optimize space as well.
If you take a closer look:

dp[i][j] = dp[i - 1][j];

It’s pretty much reusing the same value
and for

 dp[i][j] += dp[i][j - coins[i]]

We can discard the index parameter and compute the count only using the coin value itself

dp[j] += dp[j - coins[i]]

We can make sure that we are iterating from 0 to x for each coin, i.e dp[j-coins[i]] is already updated.

So our space optimized solution thus becomes:

  vector<int> dp(x + 1, 0);
  dp[0] = 1;
  for (int coin : coins) {
    for (int i = 0; i <= x; i++) {
      if (i - coin < 0)
        continue;
      dp[i] = (dp[i] + dp[i - coin]) % mod;
    }
  }
  cout << dp[x] << '\n';

Quite elegant!

Graph View