文章目录
- Tag
- 题目来源
- 解题思路
- 方法一:动态规划
- 写在最后
Tag
【动态规划】【数组】
题目来源
322. 零钱兑换
解题思路
方法一:动态规划
定义状态
dp[i]
表示凑成总金额的最少硬币个数。
状态转移
从小到大枚举要凑成的金额 i
,如果当前的金额可以使用面额数组中的某个面额 coin
凑成总金额的一部分,则可以更新
d p [ i ] = m i n ( d p [ i ] , d p [ i − c o i n ] + 1 ) dp[i] = min(dp[i], dp[i - coin] + 1) dp[i]=min(dp[i],dp[i−coin]+1)
base case
dp[0] = 0
,表示凑成总金额 0 的硬币数量为 0。
最后返回
dp[amount]
,表示凑成总金额 amount
的最少硬币个数。注意需要判断面额数组是否可以凑成指定的总金额。
实现代码
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (const auto coin : coins) {
if (coin <= i) {
dp[i] = min(dp[i], dp[i-coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
复杂度分析
时间复杂度: O ( S n ) O(Sn) O(Sn), S S S 是题目给定的需要凑成的总金额数, n n n 是面额数。我们一共需要计算 O ( S ) O(S) O(S) 个状态,每个状态需要枚举 n n n 个面额进行状态转移,所以时间复杂度为 O ( S n ) O(Sn) O(Sn)。
空间复杂度: O ( S ) O(S) O(S)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。