Leetcode -518- Change for II

[B].

// 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.
//
// You can think of an infinite number of each coin.
//
//
//
// Example 1:
//
//
// Enter: Coins = [1, 2, 5], amount = 11
// Output: 3
// 11 = 5 + 5 + 1
//
// Example 2:
//
//
// Enter: Coins = [2], amount = 3
// Output: -1
//
// Example 3:
//
//
// Enter: Coins = [1], amount = 0
// Output: 0
//
//
// Example 4:
//
//
// Enter: Coins = [1], amount = 1
// Output: 1
//
//
// Example 5:
//
//
// Enter: Coins = [1], amount = 2
// Output: 2
//
//
//
//
/ / note:
//
//
// 1 <= coins.length <= 12
// 1 <= coins[i] <= 231 - 1
// 0 <= amount <= 104
//
// Related Topics dynamic planning
// 👍 1302 👎 0
Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[Links to related topics]

Leetcode -322- Change

This site links

[introduction]

Idea 1: Recursion

• The minimum solution can be obtained based on the change above, and the total number of solutions can also be obtained. When the amount = 0 after the coins are collected, it means that the solution meets the problem requirement res+=1
• That is, we go deep through all the possibilities, combining all the results that amount=0
• In this scheme, there is no de-duplication. De-duplication can be done by increasing the number of sorts (define a coordinate that only allows coins to be fetched to the right, not to the left).

public int change(int amount, int[] coins) {
            Arrays.sort(coins);
            if (amount < 0) {
                return 0;
            }
            if (amount == 0) {
                return 1;
            }
            return dfs(coins, amount, 0.0);
        }

        public int dfs(int[] coins, int amount, int res, int index) {
            if (amount == 0) {
                return res += 1;
            }
            if (amount < 0) {
                return res;
            }
            for (int i = index; i< coins.length; i++) {
                res = dfs(coins, amount - coins[i], res,i);
            }
            return res;
        }
Copy the code

Time complexity O(amount^n^ + NLGN) n indicates the length of Coins

Idea 2: Dynamic planning

• According to the recursive equation, it can be found that there are two variable parameters. Dp [I][j] represents the number of schemes using the first I coins to meet the value of J
• First define the boundary case when j = 0 dp[I][0] = 1 when I = 0 dp[0][j] = 0(initial value)
• Recursive equation * * dp [I] [j] = dp [j] + [I – 1] sum (dp [j] [I – 1 – (j/COINS/I – 1)coins[i-1]])*

public int change(int amount, int[] coins) {
            int[][] dp = new int[coins.length + 1][amount + 1];
            for (int i = 0; i <= coins.length; i++) {
                dp[i][0] = 1;
            }
            for (int i = 1; i <= coins.length; i++) {
                int val = coins[i - 1];
                for (int j = 0; j <= amount; j++) {
                    dp[i][j] = dp[i - 1][j];
                    for (int k = 1; k <= (j / val); k++) {
                        dp[i][j] += dp[i - 1][j - k * val]; }}}return dp[coins.length][amount];
        }
Copy the code

Time complexity O(Amount * n^2^ + NLGN)n indicates the length of Coins

Idea 3: Dynamic programming (one-dimensional optimization)

• The object dimension is traversed k times in order to ensure that all elements can be traversed so that we can cancel the traversal of j and use value for traversal
• Define a dp equation dp[I] to represent the number of solutions with capacity I. The meaning of the equation is expressed as the first I coins
• The sum of all j-coins[0-length-1] is calculated and the sum of all j-coins[0-length-1] is subtracted.
• The following equation is derived: dp[I] = sum(dp[I -(val->j)]) initializing variable dp[0] = 1

public int change(int amount, int[] coins) {
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for (int i = 1; i <= coins.length; i++) {
                int val = coins[i - 1];
                for (intj = val; j <= amount; j++) { dp[j] += dp[j - val]; }}return dp[amount];
        }
Copy the code

Time complexity O(amount * n)n Indicates the length of coins