CSES - Coin Combinations I

Author: Michael Cao

In this problem, we are asked the number of ways to achieve some value, $x$ , using $n$ coins of distinct values where the order of coins does not matter. This is known as the "Unordered Coin Change" problem, which you can read about in CPH Chapter 7 under "Counting the Number of Solutions".

Main Idea

To solve this problem, let $\texttt{dp[w]}$ equal the number of ways to achieve the sum of values, $w$ . Then, for some weight $w$ , let's try to use each coin. For $\texttt{dp[w]}$ , we'll transition from $\texttt{dp[w - coin[i]]}$ for all $i$ , where $\texttt{coin[x]}$ defines the value of the $x$ -th coin.

So, the transitions are:

dp[w] = \sum_{i=1}^n{(dp[w - coins[i]])}

Warning!

Remember to take your answer mod $10^9 + 7$ , as instructed in the problem statement.

Example Code

C++

1#include <bits/stdc++.h>
2using namespace std;
3using ll = long long;
4using vi = vector<int>;
5#define pb push_back
6#define rsz resize
7#define all(x) begin(x), end(x)
8#define sz(x) (int)(x).size()
9using pi = pair<int,int>;
10#define f first

Java

Note

An otherwise working solution that uses dp[i] %= m; instead of if (dp[i] > M) dp[i] -= M; may time out on CSES, but would work on USACO, which gives double time for Java (see line 32 of the solution).

1import java.io.*;
2import java.util.*;
3
4public class CountingCoins1 {
5    static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
6    static PrintWriter pw = new PrintWriter(System.out);
7
8    public static void main(String[] args) throws IOException {
9        StringTokenizer st = new StringTokenizer(r.readLine());
10        int n = Integer.parseInt(st.nextToken());

Python

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.
We don't currently have a Python solution for this problem. Please switch to another language to view the solution code.

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum

Table of Contents