【面试经典150|动态规划】零钱兑换

文章目录 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)。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。