LeetCode 322. Change exchange (dynamic planning)

Subject portal ：322. Change for

Topic details ：

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

Topic analysis ：

After a simple analysis, it is found that it is very similar to a complete backpack , The number of coins is infinite , But the total amount （ The capacity of the backpack ） It is the same. , We are required to use the least number of coins , So we use dynamic programming to solve this problem .

First determine dp Array , The array stores the minimum number of coins required for the total amount we give , The subscript of the array is the total amount given , So we should finally return the array with the subscript amount Value , namely dp [amount];

Next, determine the recurrence equation ：

Take an example to analyze ：

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

The total amount collected 11 The minimum number of coins required is dp[11 - 5] + 1( Take the denomination as 5 The coin of , Number of coins +1), and 11-5 by 6, The total amount is 6 The minimum number of coins required is dp[6 - 5] + 1（ Then take the denomination as 5 The coin of , Number of coins +1）, And so on until the amount is 0. We found that 6 Also can be 3 The denomination is 2 Coins of , But at this time, the number of coins taken is greater than that used The denomination is 5 The coin plus the denomination is 1 The coin of 2 gold , Therefore, we should constantly select the smallest one to ensure the total amount The least number of coins . So the recurrence equation is dp[ i ]=min(dp[ i - coins[ j ] ] + 1,dp[ i ])（i For the amount that needs to be scraped up ）

dp[ 0 ]=0, Other values are initialized to the maximum value to avoid being overwritten in the comparison .

Code （c++）：

class Solution {
public:
    int max=999999999;
    int coinChange(vector<int>& coins, int amount) {
        vector<int>dp(amount+1,max);
        dp[0]=0;// The total amount is 0 You don't need a coin 
        int length=coins.size();
        for(int i=1;i<=amount;i++)// From the amount 1 Start to the requested amount amount
        {
            for(int j=0;j<length;j++)
            {
                if(coins[j]<=i) The denomination of the coin is less than the current amount 
                    dp[i]=min(dp[i-coins[j]]+1,dp[i]);
            }
        }
        if(dp[amount]==max)
            return -1;
        else
            return dp[amount];
    }
};

Computer 204 zjr