欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

零钱的兑换

程序员文章站 2022-07-13 17:36:06
...

题目: 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
示例:
示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3

解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1

思想1: 贪心算法+dfs

  1. 要想快速的凑出零钱,首先想到的就是先从大的凑,所以我们先把数组排序,把大的放在第一个或最后一个。若从小到大,我们在判断退出边界时很难判断,从大到小,我们只需判断边界是否为数组.size()即可,所以先利用反向迭代器排序为大到小。
  2. 先拿大的,拿的个数为amount/max=num个,不断从数组中取值计算,如果我们无法凑出这个整数,我们就需要把num–,再进行计算。
  3. 因为求最少硬币个数,所以要定义个ans来保存当前最小硬币数目,在比较时进行剪枝操作,即若当前硬币个数大于ans,我们则没有必要的操作
  4. 故我们可以推导出递归方程:

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:] 动态规划

  1. 这是个求解最优解的问题,我们也不难想到动态规划来解决。最优子结构性质我们不在此处进行证明了。我们知道下一次硬币的个数一定为上一次最少硬币个数加一,我们采用自上而下的解决方法。
  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