Change exchange (dynamic planning)

Give you an array of integers coins , Coins of different denominations ; There is no limit to the amount of each coin ; And an integer amount , Represents the total amount , Ask how many coins you need at least to round up the amount , If no combination of coins can make up the total amount , return -1 .

for example N = 3, The denominations are 1,2,5, Total sum amount = 11. So at least 3 A coin makes up , namely 11 = 5 + 5 + 1.

First , This problem is a dynamic programming problem , Because it has 「 Optimal substructure 」 Of . Must conform to 「 Optimal substructure 」, The subproblems must be independent of each other .

Why is it consistent with the optimal substructure ? Assuming a face value of 1, 2, 5 The coin of , seek amount = 11 Minimum number of coins per hour （ The original question ）, If you know how to come up with amount = 10, 9, 6 The minimum number of coins （ Sub problem ）, Just add one to the answer to the Subquestion （ Choose another one with a face value of 1, 2, 5 The coin of ）, Find a minimum value , It's the answer to the original question . Because there is no limit to the number of coins , So there is no interaction between subproblems , It's independent of each other .

Then according to the dynamic programming problem , List the correct state transition equations :

1.base case (amount by 0 when , The algorithm returns 0)

2.state ( Variables that will change in the original problem and subproblem ) The number of coins is unlimited , The denomination of the coin is also given by the title , Only the target amount will continue to base case near , So the only one 「 state 」 Is the target amount amount

3.choice ( Cause the state to change ) Every coin you choose , It's equivalent to reducing the target amount

4.dp ( function / Definition of array ) A recursive dp function , The parameter of a function is the quantity that will change in the state transition

dp(n) Express , Enter a target amount n, Return the rounded up target amount n The minimum number of coins required .

Solution pseudocode

int coinChange(int[]coins,int amount){
    return dp(coins,amount)
}

// Definition ： To make up the amount n, At the very least dp(coins, n) A coin
int dp(int[] coins, int n) {
    // Choose the result that needs the least coins
    for (int coin : coins) {
        result = min(res, 1 + dp(n - coin))
    }
    return result
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        if(amount<=0) return -1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int coin:coins){
            for(int i = coin; i <= amount; i++){
                dp[i] = Math.min(dp[i],dp[i-coin]+1);
            }
        }

        return dp[amount]==amount+1?-1:dp[amount];
    }
}