【LeetCode】322.零钱兑换
2021/8/13 23:05:54
本文主要是介绍【LeetCode】322.零钱兑换,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1: 输入:coins = [1, 2, 5], amount = 11 输出:3 解释:11 = 5 + 5 + 1
算法1(暴力递归)
时间复杂度:\(O(kn^k)\)
分析状态转移方程:
- 确定base case。即目标金额为0时返回0
- 确定状态,也就是原问题和子问题中会变化的量。本题中即为目标金额,随着每一次选择不同面值的硬币而递减,逐渐向base case靠近。
- 确定选择,也就是导致状态发生变化的行为。本题中即为不同面值的硬币可供选择,所以所有硬币的面值即为选择。
- 明确dp函数/数组的定义。本题的状态为目标金额的值,题目要求计算出达成目标的最少硬币个数。所以dp函数的定义为输入一个目标金额n,返回需要的最少硬币个数
伪代码:
int coinChange(int coins[], int amount) { return dp(coins, amount); } int dp(int coins, int amount) { for (auto coin : coins) { res = min(res, 1 + dp(coins, amount - coin)) } }
目标金额为0时,即零钱兑换成功,返回1,目标金额为负时,即兑换失败,返回-1。
class Solution { public: int coinChange(vector<int>& coins, int amount) { return dp(coins, amount); } int dp(vector<int>& coins, int amount) { //base case if (amount == 0) return 0; if (amount < 0) return -1; //兑换失败 int res = amount + 1; for (auto coin : coins) { //计算子问题 int subProblem = dp(coins, amount - coin); //若兑换失败则跳过 if (subProblem == -1) continue; //选择子问题最优解 res = min(res, subProblem + 1); } return (res == amount + 1) ? -1 : res; } };
很可惜,这种方法会超时,我们要采取一些优化措施。
算法2(带备忘录的递归)
分析本题的递归树,我们不难发现会有重复的计算问题,我们可以通过备忘录来减少子问题数目,消除子问题的冗余。子问题总数不超过金额数n,所以子问题个数是\(O(n)\),处理每一个子问题时有一个for循环,时间复杂度为\(O(k)\),所以整个算法的时间复杂度为\(O(kn)\)。
class Solution { public: int coinChange(vector<int>& coins, int amount) { int memo[amount + 1]; for (int i = 0; i < amount + 1; i ++ ) memo[i] = -666; return dp(coins, amount, memo); } int dp(vector<int>& coins, int amount, int memo[]) { //base case if (amount == 0) return 0; if (amount < 0) return -1; //兑换失败 if (memo[amount] != -666) { return memo[amount]; } int res = amount + 1; for (auto coin : coins) { //计算子问题 int subProblem = dp(coins, amount - coin, memo); //若兑换失败则跳过 if (subProblem == -1) continue; //选择子问题最优解 res = min(res, subProblem + 1); } memo[amount] = (res == amount + 1) ? -1 : res; return memo[amount]; } };
算法3(dp数组的迭代解法)
时间复杂度:\(O(kn)\)
算法2中我们自顶向下使用备忘录解决了冗余问题,同时我们也可以通过自底向上使用dp table消除子问题,此时dp函数体现在函数参数,dp数组体现在数组索引。
dp数组定义:dp[i]
代表兑换金额为i时最少需要dp[i]枚硬币。
class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, amount + 1); dp[0] = 0; for (int i = 0; i <= amount; i ++ ) { for (auto coin : coins) { if (i - coin < 0) continue; dp[i] = min(dp[i], dp[i - coin] + 1); } } return (dp[amount] == amount + 1) ? -1 : dp[amount]; } };
这篇关于【LeetCode】322.零钱兑换的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享