blob: 4f3c2b9f7cc0e33f1c34d1b6c89df1d329a4fd8f (
plain)
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
|
import java.util.Scanner;
public class CoinChangeDynamicProgramming {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
System.out.println(getChange(m));
}
public static int getChange(int money) {
// denominations: 1, 3, 4
int[] denominations = { 1, 3, 4 };
int[] minNumCoins = new int[money + 1];
for (int m = 1; m < minNumCoins.length; m++) {
minNumCoins[m] = Integer.MAX_VALUE;
for (int i = 0; i < denominations.length; i++) {
if (m >= denominations[i]) {
int numCoins = minNumCoins[m - denominations[i]] + 1;
if (numCoins < minNumCoins[m]) {
minNumCoins[m] = numCoins;
}
}
}
}
return minNumCoins[money];
}
}
|