当前位置：网站首页>leetcode 322. Coin change (medium)

leetcode 322. Coin change (medium)

2022-07-01 13:29:00 【InfoQ】

One 、 The main idea of the topic

label : Dynamic programming

https://leetcode.cn/problems/coin-change

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

Tips ：

1 <= coins.length <= 12

1 <= coins[i] <= 231 - 1

0 <= amount <= 104

Two 、 Their thinking

Each coin can be used infinitely many times , So it's a complete knapsack problem .dp[i] Express , Total amount reached i The minimum number of coins required , Because of the minimum number of coins, we will first dp Initialize to amount+2, The equation of state transfer is ：dp[i] = min(dp[i], dp[i-coin] + 1)

3、 ... and 、 How to solve the problem

3.1 Java Realization

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