Give coins of different denominations and an amount. Write a function to calculate the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1.

Example 1:

Enter: Coins = [1.2.5], amount = 11Output:3Explanation:11 = 5 + 5 + 1
Copy the code

Example 2:

Enter: Coins = [2], amount = 3Output: -1
Copy the code

Find the minimum number of coins needed to meet the amount required by a given amount by combining different denomination coins. We can’t find the solution directly based on the given conditions, so we have to exhaust all the possibilities and find the right solution from the possible situations. Since exhaustive, the alternatives are backtracking and dynamic programming. The amount=m+1 problem has an optimal substructure. If we know the number of coins that amount=m corresponds to, then the amount=m+1 problem also works. Therefore, dynamic programming is chosen to solve the problem.

If amount<0 amount<0 amount<0 then the result is -1. If a, M, O, u, n, t=0 amount=0 amount=0, of course it’s 0. But if amount is not one of these two special values, then you need to find the right combination of coins for a given k denominals. Given a, m, o, u, nt=n amount=n amount=n for each value m in the list of available denominations, the choices we can make are to choose or not to choose:

  • A mount−m amount -m amount−m Has an optimal solution r. If there is, then amount=n amount=n amount=n is naturally r+1 r+1 r+1. For the optimal solution of amo U nt−m amount -m amount−m, one more coin of face value M is needed
  • If not, proceed to the next possible coin value

Go through all the possible denominations, and then from all the possible results r I R_ {I} ri find the one with the smallest value, which is the optimal solution for amount=n amount=n amount=n. Therefore, the dynamic transfer equation can be written by summarizing the thinking process above:

F (n) = {0, n = < 0 0, n = 0 min ⁡ (f (n − coin ⁡) + 1, f (n)), n > 0, Coin ⁡ ∈ coin ⁡ s (n) = f \ left \ {\ begin {array} {l} 0, n = < \ \ 0, 0 n = 0 \ \ \ min (f (n – \ operatorname {“}) + 1, f (n)), n > 0, \ operatorname {coin} \ \ in operatorname {coin} {array} \ \ s end right. F (n) = ⎩ ⎨ ⎧ 0, n = < 00, n = 0 min (f (n – coin) + 1, f (n)), n > 0, coin ∈ COINS The corresponding solution code is as follows:

/ * * *@Author dyliang
 * @Date2020/8/13 * remove@Version1.0 * /
public class Solution {
    public static void main(String[] args) {
        int k = 3;
        int[] coins = {1.2.5};
        int amount = 11;

        System.out.println(helper(k, amount, coins));
    }

    private static int helper(int k, int amount, int[] coins) {
        if (amount < 0) {return -1;
        }
        if (amount == 0) {return 0;
        }

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 0; i < dp.length; i++) {
            for (int coin : coins) {
                If the amount is less than the given value, consider the next value directly
                if (i - coin < 0) {continue;
                }
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        System.out.println(Arrays.toString(dp));
        
        // If no possible combination exists for the given amount, return -1; Otherwise, the corresponding result is returned
        return (dp[amount] == mount + 1)? -1: dp[amount]; }}Copy the code