零钱的兑换
题目: 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
示例:
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
思想1: 贪心算法+dfs
- 要想快速的凑出零钱,首先想到的就是先从大的凑,所以我们先把数组排序,把大的放在第一个或最后一个。若从小到大,我们在判断退出边界时很难判断,从大到小,我们只需判断边界是否为数组.size()即可,所以先利用反向迭代器排序为大到小。
- 先拿大的,拿的个数为amount/max=num个,不断从数组中取值计算,如果我们无法凑出这个整数,我们就需要把num–,再进行计算。
- 因为求最少硬币个数,所以要定义个ans来保存当前最小硬币数目,在比较时进行剪枝操作,即若当前硬币个数大于ans,我们则没有必要的操作
- 故我们可以推导出递归方程:
dp(coins,amount-num*coin[index],index+1,count+k,ans)
其中coins为硬币数组,后面一项为当前零钱数目,index为硬币下标,count+k表示当前硬币个数,ans表示目前最少零钱个数。
看文字
理解不够深的同学可以看一下,下面这个图来理解一下,若理解了直接看代码。
简单来说就是不断递归前进找出所有情况,回溯时进行递减和剪枝操作。
代码:
void dp(vector<int>& coins, int amount, int index, int count, int& ans)
{
if (amount == 0)
{
ans = min(ans, count);//找最小值
return;
}
if (index == coins.size()) return;//越界处理
for (int k = amount / coins[index]; k >= 0 && k + count < ans; k--)//剪枝操作,回溯时k--
{
dp(coins, amount - k * coins[index], index + 1, count + k, ans);//递归
}
}
int coinChange(vector<int>& coins, int amount)
{
if(amount == 0)
return 0;
sort(coins.rbegin(),coins.rend());//从大到小
int min = INT_MAX;//用来表示最优解,每次存放最小的。
dp(coins,amount,0,0,min);
return min == INT_MAX?-1:min;//等于就表示没有计算。
}
[思想2:] 动态规划
- 这是个求解最优解的问题,我们也不难想到动态规划来解决。最优子结构性质我们不在此处进行证明了。我们知道下一次硬币的个数一定为上一次最少硬币个数加一,我们采用自上而下的解决方法。
- 推导出转移方程:
F(S-C)=F(S)+1;
C代表当前硬币的大小。F(S)为当总金额为S时的最少硬币数。
3. 假设硬币有[1,2,3] amount=4,我们画出递归树来。
在树枝上的是每次选取的硬币的数值,我们可以看到每次有大量的数值被重复计算,所以我们需要用一个数组来保存F(S)的值。
4. 我们以F(3)的求解过程来详细说明动态规划的思想:
5. 通过上面的过程我们可以总结出来,每次递归不断往下走,直至amount=0,我们返回值,不断退栈,在退栈的过程中我们用min保存最小值,不断比较,最终保存在数组中。代码: 那我们接下来看看代码:
class Solution {
vector<int>count;//设为全局的,保存最小硬币数
int dp(vector<int>& coins, int amount) {
if (amount < 0) return -1;
if (amount == 0) return 0;
if (count[amount - 1] != 0) return count[amount - 1];//例如:F(2)=F(1)+F(1)
int Min = INT_MAX;
for (int coin:coins) {
int res = dp(coins, amount - coin);//为当前最少硬币数
if (res >= 0 && res < Min) {
Min = res + 1;//加一
}
}
count[amount - 1] = Min == INT_MAX ? -1 : Min;
return count[amount - 1];
}
int coinChange(vector<int>& coins, int amount) {
if (amount < 1) return 0;
count.resize(amount);//初始化
return dp(coins, amount);
}
我最开始想到第一种,第二种比较难想,大家根据自身情况理解哦。动态规划和df有点难,我们要加油哦!❤
上一篇: 872.叶子相似的树
下一篇: BFS