Coin Change

322. Coin Change

题目链接：https://leetcode.com/problems/coin-change/#/description

题目大意：给定一堆不同面值的硬币和一个金额，要求用最少的硬币数量凑成指定的金额，相同面值的硬币可以重复使用。

题目思路：类似完全背包问题，不过不是求价值总和最大，而是求组合的硬币数最少。可以使用动态规划，res[i]表示组成金额i的最少硬币数，则有状态转移方程res[i] = min(res[i-coins[j]] + 1, res[i])。

算法复杂度分析：时间复杂度O(n*amount)，空间复杂度O(amount)

代码：

 1 class Solution {
 2 public:
 3     int coinChange(vector<int>& coins, int amount) {
 4         vector<int> res(amount + 1, -1);
 5         res[0] = 0;
 6         for (auto coin : coins)
 7             for (int c = coin; c <= amount; ++c) {
 8                 if (res[c - coin] != -1)
 9                     res[c] = res[c] != -1 ? min(res[c-coin] + 1, res[c]) : res[c-coin] + 1;
10             }
11         return res[amount] != -1 ? res[amount] : -1;
12     }
13 };

评测系统上运行结果：