LeetCode 322
https://leetcode.cn/problems/coin-change/description/
难度：中等
完全背包题目。与 0-1 背包的不同是转移方程中右边的 i 变成 i + 1，说明可以重复取同一个元素。
f[i + 1][c] = min(f[i][c], f[i + 1][c - w[i]] + v[i])
时间复杂度：O(n⋅amount)，其中 n 为 coins 的长度。
空间复杂度：O(n⋅amount)。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector f(n + 1, vector<int>(amount + 1, INT_MAX / 2)); // 除 2 防止下面 + 1 溢出
f[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int c = 0; c <= amount; c++) {
if (c < coins[i]) {
f[i + 1][c] = f[i][c];
} else {
f[i + 1][c] = min(f[i][c], f[i + 1][c - coins[i]] + 1);
}
}
}
int ans = f[n][amount];
return ans < INT_MAX / 2 ? ans : -1;
}
};