## [Leetcode]322. Coin Change(C++)

### 题目描述

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

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

### 例子

#### 例子 1

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

#### 例子 2

Input: `coins = , amount = 3` Output: `-1`

#### 例子 3

Input: `coins = , amount = 0` Output: `0`

### Constraints

• `1 <= coins.length <= 12`
• `1 <= coins[i] <= 2^31 - 1`
• `0 <= amount <= 10^4`

### 解题思路

``````minCount[i] = min(minCount[i], minCount[i - coin] + 1)
``````

``````#include <vector>

class Solution {
public:
int coinChange(std::vector<int>& coins, int amount) {
std::vector<int> minCount(amount + 1, amount + 1);
minCount = 0;

for (int i = 0; i < coins.size(); ++i) {
// iterate all possible coin
int coin = coins[i];
// iterate all amount that larger than coin
for (int j = coin; j <= amount; j++) {
minCount[j] = std::min(minCount[j], minCount[j - coin] + 1);
}
}

return minCount.back() == amount + 1 ? -1 : minCount.back();
}
};
``````
• 时间复杂度: O(amount * coins)
• 空间复杂度: O(amount)

GitHub 代码同步地址： 322.CoinChange.cpp