问题
给定不同面额的硬币 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篇文章学到一点我的经验,摸到解决动态规划问题的门槛。最后用我最喜欢的宫崎骏的动漫大集合作为本篇的封面。