零钱兑换 python,python货币兑换代码

　　如果有这样的问题，我给你一个整数数组coins，代表不同面额的硬币和一个整数金额，代表总额，计算并返回组成总额所需的最少硬币数。接下来，我将通过示例代码向您介绍Python的变更问题。有兴趣的朋友来看看吧。

　　00-1010题目：题目分析：解题思路：方案一：递归代码实现代码注释方案二：

题目：

　　题目要求用最少的硬币数算出总数。我们的第一感觉可能是用暴力或者递归来解决问题。我们用暴力解决这个问题，计算所有可能的结果，然后取最少的硬币数。时间复杂度适当为O(n ^ 3)，是一种比较慢的解题方式。在这里，我们将介绍递归解法和形而上学的位运算解法(在位运算解法有一半效率，但很难想到，所以我愿意称之为“形而上学”)。

题目分析：

解题思路：

　　五部分使用动态规划

　　1.分析并确定dp数组及其下标的含义或状态分析。

　　我们规定dp[i]是指组成I总量所需的最小硬币数。

　　2.确定递归公式。

　　我们考虑dp[i]的来源，因为dp[i]的来源是dp[i-coins[i]] 1 (coins[i]的意思是硬币中的第I个硬币)，这也是dp[i]的唯一来源。

　　那为什么1？

　　这里很清楚dp[i-coins[i]]是构成i-coins[i]量的最小硬币数。那么，当量i-coin[i]变为I时，就意味着我们在硬币中取了一个硬币coins [I]，然后从dp[i-coin[i]]变为dp[i]，就需要加上获得的硬币，也就是1。

　　通过分析dp[i]状态和之前的状态，dp[i]是最优解。

　　诸如

　　硬币=[1，2，3]数量=5

　　那么在1 1 1 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),使用有限变量。
　　

　　到此这篇关于Python零钱兑换的实现代码的文章就介绍到这了,更多相关Python零钱兑换内容请搜索盛行IT软件开发工作室以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT软件开发工作室！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

零钱兑换 python,python货币兑换代码

目录

题目：

题目分析：

解题思路：

代码实现

代码注释

解法二：

相关文章阅读