广西住房和城乡建设官方网站,dw网站建设的数据库,网站开发后台用什么语言,南宁网站推广经理文章目录 Tag题目来源解题思路方法一#xff1a;动态规划 写在最后 Tag
【动态规划】【数组】 题目来源
322. 零钱兑换 解题思路
方法一#xff1a;动态规划
定义状态
dp[i] 表示凑成总金额的最少硬币个数。
状态转移
从小到大枚举要凑成的金额 i#xff0c;如果当前… 文章目录 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(vectorint coins, int amount) {vectorint 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)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
