322. change exchange

Change for

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

reflection

dp Array meaning and its subscript meaning

dp[j]: Indicates the use of coins ( The face value of the coin is less than the amount j) Rounding up amount j The minimum number of coins

dp Array initialization

First of all, we are right coins Array to sort

Here we define

• -1 Means you can't make up the whole amount j
• 0 representative amount be equal to 0 when , You don't have to pull out a coin

First we initialize dp[0] = 0;

dp[1 …coins[0]-1 ] The assignment is -1, Because in this total amount of money j It is smaller than the smallest coin .

Secondly, initialize dp[ coins[0] ] =1, Because the total amount of money j Exactly equal to the price of the first coin So at least one coin is needed

Its remainder = Integer.Maxval;

State transition equation

dp[j] = dp[j-coins[i]] + 1;

intend We need to find the rounding up amount as j The minimum number of coins , We have coins now coins[i], So we just need to know how to make up

j-coins[i] The minimum number of coins .

So when coins[i]≤j when , We need to choose the smallest one

dp[j] =Min{dp[j-coins[0]] + 1,dp[j-coins[1]] + 1,…,dp[j-coins[i]] + 1}

that will do .

public int coinChange(int[] coins, int amount) {
    
        //  Sort array 
        Arrays.sort(coins);
        if(amount==0) return 0;
        if(amount<coins[0]) return -1;

        //  establish dp Array 
        int[] dp=new int[amount+1];

        //  initialization dp Array 
        dp[0] = 0;
        for (int i=1;i<=coins[0];i++){
    
            if(i==coins[0]) dp[i] = 1;
            else dp[i] = -1;
        }
        for (int i=coins[0]+1;i<=amount;i++){
    
            dp[i] = Integer.MAX_VALUE;
        }
        //  perfect dp Array 
        for (int i=coins[0]+1;i<=amount;i++){
    
            for (int coin : coins){
    
              if(coin<=i){
    
                  //  If the current item is equal to the backpack capacity 
                  if(i==coin) {
    
                      dp[i] = 1;
                      break;
                  }
                  //  If at present  i-coin  When the backpack cannot be loaded , That is to say i-coin=-1
                  if(dp[i-coin]==-1) continue;
                  int temp = dp[i-coin]+1;
                  if(temp<dp[i]) dp[i] =temp;
              }
            }
            //  intend   There is no one ahead dp[i-coin] Is available 
            if(dp[i]==Integer.MAX_VALUE) dp[i] =-1;
        }
        for (int i=0;i<=amount;i++){
    
            System.out.println("index="+i+","+dp[i]+ " ");
        }
        return dp[amount];
 }