This is the sixth day of my participation in the First Challenge 2022. For details: First Challenge 2022.
It rained all weekend, even from the weather forecast, it has been like this for years. But the weather had its advantages. I couldn’t go anywhere anyway, so I was reading books at home.
The title
Coins is an array of integers representing different denominations. And an integer amount representing the total amount. Calculate and return the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1. You can think of an infinite number of each coin.
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
Example 3: Input: Coins = [1], amount = 0 Output: 0
Example 4: Input: Coins = [1], amount = 11 Output: 1
Example 5: Input: Coins = [1], amount = 2 Output: 2
Train of thought
This is also a backpack problem, the requirement is just to fill the backpack, choose as few pieces as possible. Define a one-dimensional array dp, where dp[n] represents the minimum number of coins in the case that the total amount is N, and a special fixed value can be used if n cannot be exactly formed. Dp [n] = min(dp[n-coin[k]]) + 1 We can think of it this way: coins that just make up the total amount n may contain coins [0]~ coins [len-1], each with CI. Of course, CI can be 0. If ci > 0, then we can remove this coin first, so that dp[n] = dp[n-coin[k]] + 1; Since there are len coins, there can be len cases, so dp[n] = min(dp[n-coin[0]]+1… Dp [n-coin[len-1]]+1), rearrange to get the state transition equation above. The boundary condition, when amount is 0, we don’t have to use any coin, so dp[0] = 0. Dp [n] = integer.max_value; dp[n] = amount; dp[n] = amount; The number of coins must be less than amount+1, if it is equal to amount+1, it cannot be collected.
Java version code
class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount+1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i >= coin) { dp[i] = Integer.min(dp[i], dp[i-coin] + 1); } } } if (dp[amount] > amount) { return -1; } return dp[amount]; }}Copy the code