Let dp[x] be the minimum number of coins needed to make total x. Set dp[0] = 0; for every positive amount, the last coin must be one of the three denominations A, B, or C. Therefore,
dp[x] = min(dp[x - coin] + 1) over each denomination coin <= x.
Process amounts in increasing order so that dp[x - coin] already includes any number of uses of that coin. This is unbounded coin change: each denomination can be used repeatedly. The order of the three input denominations does not matter because every amount considers all three. The target is guaranteed to be reachable by the problem constraints.
Use N + 1 as the unreachable sentinel. Any reachable amount can be made with at most N coins because each denomination is a positive integer, so this sentinel is larger than every possible answer. The algorithm takes O(3N) = O(N) time and O(N) space.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.io.*;
public class Main {
static class FastScanner {
private final InputStream input = System.in;
private final byte[] buffer = new byte[1 << 16];
private int length = 0;
private int pointer = 0;
private int read() throws IOException {
if (pointer == length) {
length = input.read(buffer);
pointer = 0;
if (length == -1) return -1;
}
return buffer[pointer++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
public static void main(String[] args) throws IOException {
FastScanner scanner = new FastScanner();
int target = scanner.nextInt();
int[] coins = { scanner.nextInt(), scanner.nextInt(), scanner.nextInt() };
int unreachable = target + 1;
int[] dp = new int[target + 1];
for (int amount = 1; amount <= target; amount++) {
dp[amount] = unreachable;
for (int coin : coins) {
if (coin <= amount && dp[amount - coin] != unreachable) {
dp[amount] = Math.min(dp[amount], dp[amount - coin] + 1);
}
}
}
System.out.println(dp[target]);
}
}