@@ -0,0 +1,1735 @@
+package org.pilgrim.leetcode.y2022;%0D%0A%0D%0Aimport java.util.Arrays;%0D%0A%0D%0A/**%0D%0A * You are given an integer array coins representing coins of different%0D%0A * denominations and an integer amount representing a total amount of money.%0D%0A * Return the fewest number of coins that you need to make up that amount. If%0D%0A * that amount of money cannot be made up by any combination of the coins,%0D%0A * return -1. You may assume that you have an infinite number of each kind of%0D%0A * coin.%0D%0A *%0D%0A * Note: here provided bottom up dynamic solution algorithm with big O by time%0D%0A * in exponential O(S * n)%0D%0A */%0D%0Apublic class CoinChange3 %7B%0D%0A%09public static void main(String%5B%5D args) %7B%0D%0A%09%09int max = 0;%0D%0A%09%09for (int i = 1; i %3C= 30; i++) %7B%0D%0A%09%09%09int count = minCoinsChangeWithLimitedCoins(new int%5B%5D %7B 1, 2, 3, 5 %7D, new int%5B%5D %7B 2, 1, 2, 2 %7D, i);%0D%0A%09%09%09System.out.println(%22#%22 + i + %22: %22 + count);%0D%0A%0D%0A%09%09%09max = Math.max(max, count);%0D%0A%09%09%7D%0D%0A%0D%0A%09%09System.out.println(%22Max number of coins: %22 + max);%0D%0A%09%7D%0D%0A%09%0D%0A%09private static int minCoinsChangeWithLimitedCoins(int%5B%5D coins, int%5B%5D counts, int amount)%0D%0A    %7B%0D%0A        int%5B%5D dp = new int%5Bamount + 1%5D;%0D%0A        Arrays.fill(dp, amount + 1);%0D%0A        dp%5B0%5D = 0;%0D%0A%0D%0A        for (int i = 0; i %3C coins.length; i++) // n%0D%0A        %7B%0D%0A            int coin = coins%5Bi%5D;%0D%0A            for (int j = 0; j %3C counts%5Bi%5D; j++) // %0D%0A            %7B%0D%0A                for (int a = amount; a %3E= coin ; a--) // sum%0D%0A                %7B%0D%0A                    int remainder = a - coin;%0D%0A                    if (remainder %3E= 0)%0D%0A                    %7B%0D%0A                        dp%5Ba%5D = Math.min(dp%5Ba%5D, 1 + dp%5Bremainder%5D);%0D%0A                    %7D%0D%0A                %7D%0D%0A            %7D%0D%0A%0D%0A        %7D%0D%0A        %0D%0A        return dp%5Bamount%5D == amount + 1 ? -1 : dp%5Bamount%5D;%0D%0A    %7D%0D%0A%7D%0D%0A

add coin change machine with limit of coins