LeetCode 322. Change

322. Change for

difficulty secondary

Give you an array of integers coins , Coins of different denominations ; And an integer amount , Represents the total amount .

Calculate and return the amount needed to make up the total amount The minimum number of coins . If no combination of coins can make up the total amount , return -1 .

You can think of the number of coins of each kind as infinite .

Example 1：

 Input ：coins = [1, 2, 5], amount = 11
 Output ：3 
 explain ：11 = 5 + 5 + 1

Example 2：

 Input ：coins = [2], amount = 3
 Output ：-1

Example 3：

 Input ：coins = [1], amount = 0
 Output ：0

Tips ：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Answer key

​ When I saw this question , There are two ideas , knapsack problem , Deep search . Because coins are objects , The total amount is the backpack capacity . When I didn't put in a coin , Less the corresponding value , Then deep search recursion continues to search for the number of coins with the remaining value . But this method will time out , Because the smaller the total value , The more frequently it is called , Is there a better way to solve this problem , That is the memory search method .

Memory search method

​ When I first came into contact with the memory search method, it seemed that it was the fiboracci sequence , because f(n) = f(n-1) + f(n-2), image f(0),f(1) These will frequently recursively call , It's very inefficient , So someone came up with a way to type a watch , Is to find out all possible fiboracci sequences first , hold f(0) Switch to a[0],f(1) Switch to a[1], In this way, the calling function becomes an array element .

​ Use a backpack + When searching deeply , The biggest problem is that there are too many recursive calls , We can trade space for time , Replace the calling function with an array .

class Solution {
    
    public int coinChange(int[] coins, int amount) {
    
        if(amount < 1){
    // Total less than 1, Go straight back to 0
            return 0;
        }
        return coinChange(coins, amount, new int[amount]);
    }

    int coinChange(int[] coins, int amount, int[] count){
    
        if(amount < 0){
    // Total less than 0, return -1, It means you can't put this coin 
            return -1;
        }
        if(amount == 0){
    // The total amount is 0, It means that the coin is just right after you put it in , There is no need to put in silver coins 
            return 0;
        }
        if(count[amount - 1] != 0){
    // Replace recursive calls with arrays 
            return count[amount - 1];
        }
        int min = Integer.MAX_VALUE;
        for(int coin : coins){
    // Traverse each coin 
            int res = coinChange(coins, amount - coin, count);// Recursively call the search result set 
            if(res >= 0 && res < min){
    // The returned result is greater than or equal to 0, The result needs to be smaller than the number of coins in other enumerations , To update the minimum 
                min = 1 + res;
            }
        }
        count[amount - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[amount - 1];
    }
}

​ This method is not very efficient , Because the given data coins are in ascending order , Each enumeration is from small to large , In fact, we can also add greedy algorithm , Sort coins in descending order , Then the time complexity is reduced by pruning .

Dynamic programming

​ In fact, the knapsack problem is dynamic programming , But the memory search method is to complete the state transfer by searching the state , In this way, the time efficiency is no different from that of the search , We need to find the dynamic transfer equation .

​ The dynamic transfer equation of knapsack problem is not when traversing an object , See if you can put this item in , Then make a space in the backpack for this item , Then judge whether the current value increases .（dp[i] = max( dp[i], dp[i - w[j]])）

​ The dynamic transfer equation of the coin problem should be dp[i] = min( dp[i], dp[i - c[j]]), When put in the second i A coin , See if it makes the number of coins smaller , Update the status if it becomes smaller .

​ So the state transfer equation is ：

• When i = 0 when ,dp[ i ] = 0
• When i > 0 when ,dp[ i ] = min(dp[ i - c[ j ] ], dp[ i ])

class Solution {
    
    public int coinChange(int[] coins, int amount) {
    
        int max = amount + 1;
        int[] dp = new int[amount + 1];// The dynamic array 
        Arrays.fill(dp, max);// Fill the array with the maximum value , The number of coins will not exceed the capacity of the array  + 1
        dp[0] = 0;// initialization 
        for(int i = 1; i <= amount; i++){
    // Traversal state 
            for(int j = 0; j < coins.length; j++){
    // Traverse coins 
                if(coins[j] <= i){
    // The total amount is greater than the face value of the coin 
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);// Dynamic transfer equation 
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}