322. 零钱兑换
题目描述
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
测试样例
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
数据范围
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
算法
完全背包问题。
-
相当于有 $n$ 种物品
-
每种物品的体积是硬币面值,价值是1
-
问装满背包最少需要多少价值的物品
状态表示: f[j]
表示凑出 $j$ 价值的钱,最少需要多少个硬币。
第一层循环枚举不同硬币,第二层循环从小到大枚举所有价值(由于每种硬币有无限多个,所以要从小到大枚举),然后用第 $i$种硬币更新 f[j]
:f[j] = min(f[j], f[j - coins[i]] + 1)
。
时间复杂度
$O(nm)$,$n$ 表示硬币种数,$m$ 表示总价钱
代码
class Solution {
public:
int coinChange(vector<int>& coins, int m) {
int n = coins.size();
// 初始化 f[0][]
vector<int> f(m + 1, 2e9);
f[0] = 0;
for(auto v:coins)
for(int j = v; j <= m; j ++)
f[j] = min(f[j], f[j - v] + 1);
if(f[m] == 2e9)
return -1;
else
return f[m];
}
};