[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 = [2], amount = 3 Output: -1

例子 3

Input: coins = [1], amount = 0 Output: 0

Constraints

1 <= coins.length <= 12

1 <= coins[i] <= 2^31 - 1

0 <= amount <= 10^4

解题思路

这道题从数据规模来看应该用动态规划来做。思路是建立一个长度为 amount + 1 的数组 minCount，其中 minCount[i] 表示使用给定的 coin 来组成 i 的面值需要的最小数量。

通过从小面值的 coin 来开始遍历，每次遍历一遍数组时，转移方程为：

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

即比较当前值和，和当前值减去当前候选硬币值再加 1 即可。

代码如下：

#include <vector>

class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        std::vector<int> minCount(amount + 1, amount + 1);
        minCount[0] = 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

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions