diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources/CoinChangeDynamicProgramming.java')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/CoinChangeDynamicProgramming.java | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/CoinChangeDynamicProgramming.java b/AlgoDesignAndTechniqueEdxJava/sources/CoinChangeDynamicProgramming.java new file mode 100644 index 0000000..4f3c2b9 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxJava/sources/CoinChangeDynamicProgramming.java @@ -0,0 +1,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]; + } + +} |