# Question

Formatted question description: https://leetcode.ca/all/322.html

 322	Coin Change

You are given coins of different denominations and a total amount of money amount.
Write a function to compute the fewest number of coins that you need to make up that amount.

If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

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

Note:
You may assume that you have an infinite number of each kind of coin.

@tag-dp


# Algorithm

We maintain a one-dimensional dynamic array dp, where dp[i] represents the change of the smallest number of coins when the amount of money is i. Note that since the array starts from 0, one more bit must be applied. The size of the array is amount +1, so the final result can be saved in dp[amount].

Initialize dp[0] = 0, because if the target value is 0, no coins are needed. Other values ​​can be initialized as amount+1, why? Because the smallest coin is 1, so amount requires at most amount coins, and amount+1 is equivalent to the current maximum.

• Note that the integer maximum value cannot be used for initialization here, because there is an operation of adding 1 to the subsequent state transition equation, which may cause overflow.

The next step is to find the state transition equation. Example 1, suppose I take a coin with a value of 5, then since the target value is 11, so if we know dp[6], then we know the dp of 11 Worth it?

So the way to update dp[i] is to traverse each coin. If the value of the traversed coin is less than the value of i (for example, a coin with a value of 5 cannot be used to update dp[3]), use dp[i-coins[j ]] + 1 to update dp[i], so the state transition equation is:

dp[i] = min(dp[i], dp[i-coins[j]] + 1);


among them

• coins[j] is the j-th coin
• i-coins[j] is the amount of money i minus the value of one of the coins, the remaining amount of money is found in the dp array

Then add 1 and compare the value in the current dp array, and update the dp array with the smaller one.

Java