CSES - Minimizing Coins

Authors: Michael Cao, Sofia Yang, Paul Chen

Edit This Page

Table of Contents

Main IdeaImplementation

In this problem, we're asked the minimum number of coins of distinct weights needed to achieve some weight, xx. You can read about the solution to this classical problem in CPH Chapter 7 under "Coin Problem".

Main Idea

For this problem, we'll define dp[w]\texttt{dp[w]} as the minimum number of coins to achieve some weight, ww. Then, at some ww, we can try to use every coin. Using the ii-th coin represents transitioning from the state dp[w - coins[i]]\texttt{dp[w - coins[i]]} where coins[i]\texttt{coins[i]} represents the value of the ii-th coin. So, for dp[i]\texttt{dp[i]}, the transition is:

dp[w]=min⁡i=1n(dp[w−coins[i]])+1dp[w] = \min_{i=1}^n{(dp[w - coins[i]]) + 1}

Finally, the base case would be dp[0]=0\texttt{dp[0]} = 0, since it requires 00 coins to get a sum of 00.

Warning!

Remember to initialize the dp\texttt{dp} array with some large value, since we are computing a minimum. Additionally, if dp\texttt{dp} is an int array, don't initialize dp\texttt{dp} with INT_MAX, since that could cause overflow when you add 1 for the transitions.

Warning!

Don't forget to check if dp[x]=MX\texttt{dp[x]} = MX, where MXMX is the large value you used, and print −1-1 if so (since it's impossible to achieve a sum of xx).

Implementation

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

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class cses1634 {
	public static int MAX = (int)10e6 + 2;


	public static void main(String[] args) throws IOException {
		BufferedReader br =

Python

INF = 1000000000  # Using float('inf') results in a TLE


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


dp = [INF] * (x + 1)
dp[0] = 0  # Base case: 0 coins are needed for a sum of 0


for i in range(x):
	# Continue if the state is impossible

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