Python零钱兑换
亖夕 人气:0题目：
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins =
[1, 2, 5], amount =11输出：
3解释说明：11 = 5 + 5 + 1
示例 2：
输入：coins =
[2], amount =3输出：-1
解释说明：硬币无法凑成金额-1
示例 3：
输入：coins = [1], amount = 0
输出：0
题目分析：
题目要求用最少的硬币个数凑出总金额amount。我们第一感觉可能是使用暴力或者递归解题，对这道题使用暴力解题，计算出所有可能的结果后取硬币数最小值，时间复杂度妥妥O(n^3），算是很慢的解题方式了，下面我们介绍递归解法和玄学位运算解法（使用到位运算解法的解题效率一半很高，但是很难想到，所以我愿称之为“玄学”）
解题思路：
解法一：递归
使用动态规划五部曲
1.分析确定dp数组以及其下标的含义或状态分析
我们规定dp[i]表示凑足总额为 i 所需钱币的最少个数。
2.确定递推公式
我们考虑dp[i]的来源，因为dp[i]的来源为dp[i - coins[i]] + 1，（coins[i]表示coins中的第i枚硬币），这也是dp[i]的唯一来源。
那为什么要+1呢？
这里我们明确dp[i - coins[i]]是凑够金额 i - coin[i]的最少硬币个数。那么当金额i - coin[i]变到 i 时，意味着我们在coins中拿了一枚硬币coins[i]，那么从dp[i - coin[i]] 到 dp[i]需要加上所取得那枚硬币，即+1.
分析到dp[i]状态及前面得状态，dp[i]即为最优解。
---------------------------------------
如
coins = [1, 2, 3] amount = 5
那么在 1+1+1+1+1 = 5, 1+2+1+1 = 5, 2+2+1 = 5....等情况中
dp[5]最优解必为2+2+1 = 5
即dp[5] = dp[5 - coins[0]] + 1
而dp[5 - coins[0]] = dp[4] = dp[4 - coins[1]] + 1
以此类推
------------------------------------------
我们要取最优解（硬币数最少）也就是取dp[i - coins[i]] + 1最小值
即递推公式为：dp[i] = min(dp[i - coins[i]] + 1， dp[i])
(括号中得dp[i]为上一状态的dp[i])
3.如何初始化dp数组
我们分析公式的基础，可得公式基础为dp[0]即凑足总额为 0 所需钱币的最少个数。接着考虑到其他dp列表其他下标的初始化，由于递推公式使用了min（），那么为了不让初始化影响递推结果，我们需要将dp[i]（i != 0)初始化为一个很大的数，如正无穷‘inf’。
4.确定遍历的顺序
题目要求的是找到最小硬币个数，所以遍历coins或者先遍历寻找amount列表无关紧要。
5.举例验证推导的dp数组（公式）是否正确
可以带入一个简单以的例子，比如例1.
代码实现
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1代码注释
def coinChange(coins, amount):
# 初始化dp列表
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 初始化递推公式基础
for coin in coins: # 遍历硬币
# 遍历寻找构成amount最优解
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
# 如果最终没有找到凑成amount金额的硬币，返回-1
return dp[amount] if dp[amount] != float('inf') else -1时间复杂度O(nm),n为amoun面额，m为硬币种数。空间复杂度为O(m),即为dp列表所用空间。
解法二：
接下来就是玄学位运算了。先看代码
代码实现
def coinChange(coins, amount):
if not amount:
return 0
dp = 1 << amount
res = 0
while dp:
tmp = 0
res += 1
for i in coins:
tmp |= dp >> i
if tmp & 1:
return res
dp = tmp
return -1代码注释
def coinChange(coins, amount):
if not amount:
return 0
# 按位左移运算构造类似dp数组的记录二进制
dp = 1 << amount
res = 0
while dp: # dp = 0或return 时循环结束
tmp = 0 # tmp用于临时记录和承接上一个dp二进制
res += 1 # res为最终答案
for i in coins:
# 利用按位右移不断右移。利用按位或运算
# 将前一次按位右移运算与后一次按位右移运算合并
tmp |= dp >> i
if tmp & 1: # 当tmp最后位数为1时res即为答案，返回res
return res
dp = tmp
return -1位运算解法过程我打印出来了，不清楚的可以看看
def coinChange(coins, amount):
if not amount:
return 0
dp = 1 << amount
res = 0
while dp:
print('dp:', bin(dp))
tmp = 0
print('tmp:', bin(tmp))
res += 1
print('res:', res)
for i in coins:
print('i:', i)
tmp |= dp >> i
print('ys_tmp:', bin(tmp))
print('--------------')
if tmp & 1:
return res
dp = tmp
return -1输出
dp: 0b100000000000
tmp: 0b0
res: 1
i: 1
ys_tmp: 0b10000000000
--------------
i: 2
ys_tmp: 0b11000000000
--------------
i: 5
ys_tmp: 0b11001000000
--------------
dp: 0b11001000000
tmp: 0b0
res: 2
i: 1
ys_tmp: 0b1100100000
--------------
i: 2
ys_tmp: 0b1110110000
--------------
i: 5
ys_tmp: 0b1110110010
--------------
dp: 0b1110110010
tmp: 0b0
res: 3
i: 1
ys_tmp: 0b111011001
--------------
i: 2
ys_tmp: 0b111111101
--------------
i: 5
ys_tmp: 0b111111101
--------------
虽然难理解，但是解题效率不是一般的高
时间复杂度O(n),n为coins长度。空间复杂度O(1),使用有限变量。
加载全部内容