动态规划系列之九找零钱

问题

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
你可以认为每种硬币的数量是无限的。

coins = [1,2,5]
amount = 11
结果:3,硬币为:5,5,1

解决过程

解题思路

动态规划解题思路是:将大的问题拆解成小一点问题,小问题和大问题的解决思路是类似的
给定一个总金额11,有三种硬币:1,2,5。
将问题的规模减少:凑11难凑,就凑10,如果10难凑就凑9,一直到凑1,凑0。

建立数学模型

添加数组dp,表示凑到某一个数值的最小硬币数。如dp[1]就代表金额为1的最少硬币数,dp[10]就代表金额为10的最少硬币数。该dp数组长度为12,从金额为0到11,初始化为:

[12,12,12,12,12,12,12,12,12,12,12,12]

之所以初始化为12,是总金额+1,因为可能会存在凑不到这个数的情况。当凑不到时,dp[-1]=12,凑得到时,即使硬币金额最小为1,也只用11即可。

状态转移方程

当要凑成的金额为0时:

dp = [0,12,12,12,12,12,12,12,12,12,12,12]

金额为1时
由于硬币有 1、2、5,所以,金额大于硬币1的数额,所以一块硬币价值为1即可

dp = [0,1,12,12,12,12,12,12,12,12,12,12]

金额为2时
金额为2是,金额大于硬币1,硬币2,所以有两种方案可以凑齐。
1、某一个金额加上硬币2,那么就是金额0 + 硬币2 dp[0] = 0,所以dp[2] = 1
2、某一个金额加上硬币1,那么就是金额1 + 硬币1 dp[1] = 1,所以dp[2] = dp[1] + 1 = 2

选择最小的,所以dp[2] = 1

dp = [0,1,1,12,12,12,12,12,12,12,12,12]

金额为3时
金额大于硬币1,硬币2,所以有两种方案
某一个金额加上硬币2,就是 金额1 + 硬币2 dp[3-2] + 1。dp[3-2],意思就是金额3减去硬币2,得到的金额1其最小的组成硬币数。dp[3] = dp[3-1] + 1 = 2

某一个金额加上硬币1,就是 金额2 + 硬币1 dp[3-1] + 2。dp[3-1],意思就是 金额3 – 硬币1,得到的金额其最小组成的硬币数。dp[3] = dp[3-2] + 1 = 2
所以,金额3时,dp[3] = 2

dp = [0,1,1,2,12,12,12,12,12,12,12,12]

金额为4时
金额大于硬币1,硬币2,所以有两种方案
金额为2 + 硬币2,即 dp[4-2] + 1,dp[4] = 2
金额为3 + 硬币1,即 dp[4-1] + 1,dp[4] = 3
所以,金额为4时,dp[4] = 2

dp = [0,1,1,2,2,12,12,12,12,12,12,12]

金额为5时
金额大于硬币1,硬币2,硬币5,所以有三种方案
金额为4 + 硬币1,即 dp[5-1] + 1,dp[5] = 2 + 1 = 3
金额为3 + 硬币2,即 dp[5-2] + 1,dp[5] = 2 + 1 = 3
金额为0 + 硬币5,即 dp[5-5] + 1,dp[5] = 1
所以,dp[5] = 1

dp = [0,1,1,2,2,5,12,12,12,12,12,12]

最终按照这个规律,算出dp所有的数值。

代码

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

def coinChange(coins, amount):
    # 构建dp动态数组
    dp = [amount + 1] * (amount + 1)
    # 初始化
    dp[0] = 0
    
    for i in range(1, amount + 1):
        # 每一个金额,所有能凑成的方案的硬币数,最后取最小值
        temp = [dp[i]]
        for coin in coins:
            # 当金额大于某一个硬币时才考虑,否则一定无法用大额硬币凑成小额
            if i >= coin:
                temp.append(dp[i-coin]+1)
        dp[i] = min(temp)
    print(dp)
    return -1 if dp[-1] == amount + 1 else dp[-1]

coins = [1, 2, 5]
amount = 11
res = coinChange(coins, amount)
print(res)

小结

动态规划系列到这一篇就算完结了,个人感觉动态规划是算法中很有难度,有技巧,有魅力的一种算法。为了学明白这一种算法,我也很多次在深夜里思考求解。当我觉得自己似乎掌握了浅显的规律之后,就把它记录下来。这当然是我个人不太成熟的思想,动态规划的深奥远不是我能用9篇文章说明白的。但是,希望读者能从这9篇文章学到一点我的经验,摸到解决动态规划问题的门槛。最后用我最喜欢的宫崎骏的动漫大集合作为本篇的封面。

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

【ZeyFraのJavaEE开发小知识05】Mybatis-Plus & Axios

2021-3-16 22:00:00

经验教程

不求甚解的深度学习教程(1)-逻辑回归基本概念以及代价函数

2021-3-16 23:17:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索