DSA sheet / Dynamic programming
Coin Combinations I
Do these first: Dice Combinations, Minimizing Coins
The problem in brief
You have n distinct coin values (n up to 100) available in unlimited quantity. Given a target x (up to 10^6), print the number of ways to produce exactly x when the order in which coins are used matters, modulo 10^9 + 7.
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/1635.
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.
-
This looks like Dice Combinations with different step sizes. What plays the role of the six die faces?
-
Condition on the last coin used. What remains to be paid, and how many ways are there for it?
-
Because order matters, the sequence “2 then 3” and “3 then 2” are different. Which loop nesting (targets outside, coins inside, or the reverse) counts sequences rather than multisets?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Recognise the pattern: this is the same recurrence as dice throws, with the die faces replaced by the coin values. ways[s] = sum over coins c <= s of ways[s - c], with ways[0] = 1.
The important subtlety is the loop order, because the next problem in this sheet asks for the same setup but counts unordered combinations and needs the loops swapped. If the outer loop runs over the total s and the inner loop over coins, then at each total you consider every coin as the last one, so each ordering of the same coins is counted separately: that is exactly “order matters”. Learn to tell the two apart: outer = target counts sequences, outer = coin counts multisets.
Intuition
To build total s as a sequence, look at its final coin. Whatever came before is any sequence for the smaller total. Add up over all possible final coins.
Approach
- ways[0] = 1, everything else 0.
- For s from 1 to x, for each coin c with c <= s: ways[s] = (ways[s] + ways[s - c]) mod (10^9 + 7).
- Print ways[x].
Pitfalls: keep the accumulation in a type that does not overflow (two values below the modulus sum to less than 2 * 10^9 + 14, so reduce after each addition, or use 64-bit); target 0 is not asked. Work is n * x, up to 10^8 simple steps (fine in C++/Java; use PyPy for Python).
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 MOD = 1000000007;
vector<int> ways(x + 1, 0);
ways[0] = 1;
for (int s = 1; s <= x; s++) {
for (int c : coins) {
if (c <= s) {
ways[s] += ways[s - c];
if (ways[s] >= MOD) ways[s] -= MOD;
}
}
}
printf("%d\n", ways[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]))
MOD = 10**9 + 7
ways = [0] * (x + 1)
ways[0] = 1
for s in range(1, x + 1):
total = 0
for c in coins:
if c <= s:
total += ways[s - c]
ways[s] = total % MOD
print(ways[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 MOD = 1_000_000_007;
int[] ways = new int[x + 1];
ways[0] = 1;
for (int s = 1; s <= x; s++) {
for (int c : coins) {
if (c <= s) {
ways[s] += ways[s - c];
if (ways[s] >= MOD) ways[s] -= MOD;
}
}
}
System.out.println(ways[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 MOD = 1000000007;
const ways = new Int32Array(x + 1);
ways[0] = 1;
for (let s = 1; s <= x; s++) {
let total = 0;
for (const c of coins) {
if (c <= s) total += ways[s - c];
}
ways[s] = total % MOD;
}
console.log(ways[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).