DSA sheet / Dynamic programming
Minimizing Coins
Do these first: Dice Combinations
The problem in brief
You have n coin values (n up to 100, each up to 10^6) and may use each value any number of times. Given a target x (up to 10^6), print the smallest number of coins that sum to exactly x, or -1 if it cannot be done.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1634.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Greedily taking the biggest coin sometimes fails. Try coins 1, 3, 4 and target 6 to see why.
-
Think recursively about the last coin used. If you knew the best answer for every smaller target, what would the answer for x be?
-
Define best[s] as the fewest coins for total s. Which entries does best[s] depend on, and what is best[0]?
-
Some totals are unreachable. How do you represent that so that “unreachable plus one coin” does not accidentally look reachable?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Coin change is the standard example where greedy is wrong and DP is right. You can defend that by finding a counterexample (coins 1, 3, 4 with target 6: greedy takes 4 + 1 + 1 = 3 coins, but 3 + 3 = 2 coins is better). Once greedy is out, use the recipe: state, transition, base case.
State: best[s], the fewest coins for total s. Transition: whichever coin c was used last, best[s] = 1 + best[s - c]; choose the minimum over all c <= s. Base: best[0] = 0. Unreachable totals get a big sentinel value (bigger than any real answer but small enough not to overflow when you add 1).
This is unbounded knapsack: the same item may be reused, which is why a single left-to-right pass over s (rather than a reversed pass) is correct.
Intuition
To pay s, decide which coin you hand over last. The rest has to be paid exactly, and you already know the cheapest way to pay every smaller amount. Try each coin and keep the cheapest total.
Approach
- best[0] = 0 and best[s] = INF for s from 1 to x, with INF such as 10^9.
- For s from 1 to x, for each coin c <= s: best[s] = min(best[s], best[s - c] + 1).
- Print best[x], or -1 if it is still INF.
Pitfalls: INF + 1 must not overflow (10^9 + 1 is fine in 32 bits); the number of coins needed is at most x itself. Work is n * x, up to 10^8, which is fine in C++ and Java. CPython is too slow at the maximum limits, so submit Python solutions as PyPy on judges that offer it.
Complexity
O(n * x) time, O(x) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
scanf("%d %d", &n, &x);
vector<int> coins(n);
for (auto &c : coins) scanf("%d", &c);
const int INF = 1000000000;
vector<int> best(x + 1, INF);
best[0] = 0;
for (int s = 1; s <= x; s++) {
for (int c : coins) {
if (c <= s && best[s - c] + 1 < best[s]) best[s] = best[s - c] + 1;
}
}
printf("%d\n", best[x] >= INF ? -1 : best[x]);
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
coins = list(map(int, data[2:2 + n]))
INF = 10**9
best = [INF] * (x + 1)
best[0] = 0
for s in range(1, x + 1):
m = INF
for c in coins:
if c <= s:
v = best[s - c] + 1
if v < m:
m = v
best[s] = m
print(-1 if best[x] >= INF else best[x])
main() # heavy at the maximum limits: submit as PyPy 3 on judges that have itimport java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int x = (int) st.nval;
int[] coins = new int[n];
for (int i = 0; i < n; i++) {
st.nextToken();
coins[i] = (int) st.nval;
}
final int INF = 1_000_000_000;
int[] best = new int[x + 1];
java.util.Arrays.fill(best, INF);
best[0] = 0;
for (int s = 1; s <= x; s++) {
for (int c : coins) {
if (c <= s && best[s - c] + 1 < best[s]) best[s] = best[s - c] + 1;
}
}
System.out.println(best[x] >= INF ? -1 : best[x]);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const x = data[1];
const coins = data.slice(2, 2 + n);
const INF = 1e9;
const best = new Int32Array(x + 1).fill(INF);
best[0] = 0;
for (let s = 1; s <= x; s++) {
for (const c of coins) {
if (c <= s && best[s - c] + 1 < best[s]) best[s] = best[s - c] + 1;
}
}
console.log(best[x] >= INF ? -1 : best[x]);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).