LeetCode //C - 322. Coin Change

本文主要是介绍LeetCode //C - 322. Coin Change，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

322. Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return 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.

You may assume that you have an infinite number of each kind of 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

Constraints:

-1 <= coins.length <= 12

• $1<=coins[i]<=2^{31}-1$
• $0<=amount<=10^4$

From: LeetCode
Link: 322. Coin Change

---

Solution:

Ideas：

1. Initialize an array dp of size amount + 1 and fill it with amount + 1. This value acts as a placeholder for an unattainable number of coins (since it’s impossible to have more coins than the amount itself).
2. Set dp[0] = 0 because no coins are needed for the amount 0.
3. Iterate through each amount from 1 to amount.
4. For each amount, iterate through the array of coins.
5. If the coin value is less than or equal to the current amount, update dp[amount] to be the minimum of dp[amount] and dp[amount - coin] + 1.
6. After filling the table, check dp[amount]. If it’s still amount + 1, it means the amount cannot be formed by the given coins, so return -1. Otherwise, return dp[amount].

Code:

int coinChange(int* coins, int coinsSize, int amount) {int dp[amount + 1];for (int i = 0; i <= amount; i++) {dp[i] = amount + 1;}dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int j = 0; j < coinsSize; j++) {if (coins[j] <= i) {dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;}}}return dp[amount] > amount ? -1 : dp[amount];
}

这篇关于LeetCode //C - 322. Coin Change的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---