标签搜索

目 录CONTENT

文章目录

凑零钱问题.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 2,847 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-21,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

凑零钱问题

@

https://leetcode.cn/problems/coin-change/

一、问题描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算

可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例 1:

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

示例 2:

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

你可以认为每种硬币的数量是无限的。

方法一: 暴⼒递归[超时]

  • ⾸先, 这个问题是动态规划问题, 因为它具有「最优⼦结构」 的。 要符合「最优⼦结构」 , ⼦问题间必须互相独⽴。
  • 为什么说它符合最优⼦结构呢? ⽐如你想求 amount =11 时的最少硬币数(原问题) , 如果你知道凑出 amount = 10 的最少硬币数(⼦问题) , 你只需要把⼦问题的答案加⼀(再选⼀枚⾯值为 1 的硬币)就是原问题的答案, 因为硬币的数量是没有限制的, ⼦问题之间没有相互制, 是互相独⽴的。
  • 那么, 既然知道了这是个动态规划问题, 就要思考如何列出正确的状态转移⽅程?
  • 先确定**「状态」** , 也就是原问题和⼦问题中变化的变量。 由于硬币数量⽆限, 所以唯⼀的状态就是⽬标⾦额 amount 。然后确定 dp 函数的定义: 当前的⽬标⾦额是 n , ⾄少需要 dp(n) 个硬币凑出该⾦额
  • 然后确定**「选择」** 并择优, 也就是对于每个状态, 可以做出什么选择改变当前状态。 具体到这个问题, ⽆论当的⽬ 标⾦额是多少, 选择就是从⾯额列表coins 中选择⼀个硬币, 然后⽬ 标⾦额就会减少:
# 伪码框架
def coinChange(coins: List[int], amount: int):
	# 定义: 要凑出⾦额 n, ⾄少要 dp(n) 个硬币
	def dp(n):
		# 做选择, 选择需要硬币最少的那个结果
		for coin in coins:
			res = min(res, 1 + dp(n - coin))
	return res
	# 我们要求的问题是 dp(amount)
return dp(amount)

最后明确 base case, 显然⽬ 标⾦额为 0 时, 所需硬币数量为 0; 当⽬ 标⾦额⼩于 0 时, ⽆解, 返回 -1:

def coinChange(coins: List[int], amount: int):
	def dp(n):
		//base case
		if n == 0: return 0
		if n < 0: return -1
		//求最⼩值, 所以初始化为正⽆穷
		res = float('INF')
		for coin in coins:
			subproblem = dp(n - coin)
		//⼦问题⽆解, 跳过
		if subproblem == -1: continue
		res = min(res, 1 + subproblem)
	return res if res != float('INF') else -1
return dp(amount)

完整代码

class Solution {
public:

    int dp(vector<int>& coins,int amount)
    {
        if(amount == 0)//递归出口,当amount递归到为0时,代表找到合适当零前
        {
            return 0;
        }

        if(amount < 0)//递归出口,当amount递归到小于0时,代表某一趟未找到合适到零钱
        {
            return -1;
        }

        int res = INT_MAX;//记录最后所需到硬币个数,开始定义为最大值,因为下面求的是最小值
        for(auto e : coins)//遍历所有到硬币面额,暴力寻找合适到零钱
        {
            int temp = dp(coins,amount - e);//temp代表 amount - e 后到金额所需硬币的个数 
            if(temp == -1)//如果temp == -1;代表该趟寻找零钱到路径不合适,continue继续判断下一个硬币金额
            {
                continue;
            }

            //走到这里代表成功找到合适到零钱,把这次找到合适零钱所用到到硬币个数和上一次进行比较
            res = min(res,1 + temp);//+1 意思是 amount - e 金额所需到硬币个数加上 e 金额所需到1个硬币
        }

        if(res == INT_MAX)//如果res未改变,代表没有任何一种方式可以找零钱,return -1
        {
            return -1;
        }

        return res;

    }
    int coinChange(vector<int>& coins, int amount) {
        return dp(coins,amount);
    }
};

方法二:带备忘录到递归

外加一个vector记录计算过的值,减少重复计算

class Solution {
public:

    int dp(vector<int>& coins, int rem, vector<int> &count)
    {
        if (rem < 0) 
            return -1;

        if (rem == 0) 
            return 0;

        // != 0 代表count[rem - 1]已经计算过且保存在count中,直接返回,不用重复计算
        if (count[rem - 1] != 0)
             return count[rem - 1];

        int min = INT_MAX;
        for (int coin : coins) 
        {
            int res = dp(coins, rem - coin, count);

            if (res >= 0 && res < min)
                min = 1 + res;
        }

        //保存结果,为下一次的计算减轻负担
        count[rem - 1] = (min == INT_MAX) ? -1 : min;
        return count[rem - 1];

    }
    

    int coinChange(vector<int>& coins, int amount) {
    
    if (amount < 1) 
        return 0;

    vector<int> count(amount);//传递一个数组用来记录计算过到值,避免重复计算
        return dp(coins, amount, count);
    }
};


方法三:dp数组的迭代

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //空间大小为amount + 1,初始值也为amount + 1;因为最小的硬币面值为1,应该不会出现面值为0.5的硬币~~~
        vector<int> dp(amount + 1,amount + 1);

        dp[0] = 0;//相当于递归出口,用来计算,因为当金额为0时就不再需要硬币了,这里不能是amount + 1,
        for(int i = 0;i < dp.size();i++)
        {
            for(auto e : coins)
            {
                if(i - e < 0)
                {
                    continue;
                }

                dp[i] = min(dp[i],1 + dp[i - e]);
            }
        }
        if(dp[amount] == amount + 1)
        {
            return -1;
        }
        return dp[amount];
    }
};
0

评论区