CSES - Coin Combinations I

Author: Michael Cao

Edit This Page

Table of Contents

ExplanationImplementation

Explanation

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

So, the transition is

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

Implementation

Time Complexity: O(N⋅X)\mathcal{O}(N \cdot X)

C++

#include <iostream>
#include <vector>


using std::cout;


const int MOD = 1e9 + 7;


int main() {
	int n, x;
	std::cin >> n >> x;

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

import java.io.*;
import java.util.*;


public class CountingCoins1 {
	static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw = new PrintWriter(System.out);


	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(r.readLine());
		int n = Integer.parseInt(st.nextToken());

Python

Warning!

Due to Python's large constant factor, the solution below TLEs on a couple of test cases.

MOD = 10**9 + 7


n, x = map(int, input().split())
coins = list(map(int, input().split()))


dp = [0] * (x + 1)
dp[0] = 1
for i in range(1, x + 1):
	for c in coins:
		if i - c >= 0:
			dp[i] = (dp[i] + dp[i - c]) % MOD


print(dp[x])

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