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]; } }