Topic describes

Algorithm thought

To illustrate the idea of the algorithm, suppose you have an array [1,2,3] and find the minimum number of coins in the array to make note 6.

The number of dp[0] dp[1] dp[2] dp[3] dp[4] dp[5] dp[6]
For the first time, 0 1(dp[0]+1) 2(dp[1]+1) 3(dp[2]+1) 4(dp[3]+1) 5(dp[4]+1) 6(dp[5]+1)
The second time 0 1 1(dp[0]+1) 2(dp[1]+1) 2(dp[2]+1) 3(dp[3]+1) 3(dp[4]+1)
The third time 0 1 1 1(dp[0]+1) 2(dp[1]+1) 2(dp[2]+1) 2(dp[3]+1)

There are two levels of traversal. The first level of traversal is to find the minimum number of coins in [0,0] that are needed for all [0,6] of these notes.

The second layer uses the value of the array [0,1] and the second layer finds the minimum number of coins in [0,1] needed for all [0,6].

The third is the first layer to loop through the array [0,2] and the second layer to find the minimum number of [0,2] of all the [0,6] notes that need one of [0,2].

In short, you take the previous result and add a number to it and see if you can minimize the number of coins you use.

Code implementation

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, 1, amount+1, Integer.MAX_VALUE);

        for(int i = 0; i < coins.length; i++){
            for(int j = coins[i]; j <= amount; j++){
                if(dp[j - coins[i]] ! = Integer.MAX_VALUE){ dp[j] = Math.min(dp[j], dp[j - coins[i]] +1); }}}if(dp[amount] ! = Integer.MAX_VALUE){return dp[amount];
        }
        return -1; }}Copy the code