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];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17