Python换钱的最少货币数
题⽬：
给定数组arr，arr中所有的值都为正数且不重复。每个值代表⼀种⾯值的货币，每种⾯值的货币可以使⽤任意张，再给定⼀个整数aim，代表要的钱数，求组成aim的最少货币数。
例：
arr = [5, 2, 3]，aim = 20，arr中组成20的最少张数为4，返回4。
arr = [5, 2, 3]，aim = 0，不⽤任何货币就可以组成0，返回0。
arr = [3, 5]，aim = 2，钱不开返回-1 。
python货币转换
思路：
假设arr = [5, 2, 3]，aim=10。
建⽴⼀个N*(M+1)的矩阵dp，N为arr⾥的个数，M=aim，dp[i][j]表⽰由当前⾏及该⾏上⾯所有⾏的货币种类兑换该列值的最少货币数，所在的列即需要兑换的钱数，dp初始化如下：
⾏\列012345678910
500000000000
200000000000
300000000000
⾸先，计算第⼀⾏可兑换的钱数，即⽤5能兑换的钱数，其它不可兑换的钱数⽤max表⽰，如下：
⾏
012345678910
\列
50max max max max1max max max max2
2
3
计算其它位置。对于dp[i][j]，当前i⾏兑换j钱数时，m为i⾏对应的货币值，若dp[i][j]可以兑换开，则dp[i][j-m]位置也可以兑换，此时dp[i][j] = dp[i][j-m] + 1。同时需要对⽐上⼀⾏兑换该钱数使⽤的货币数，即dp[i-1][j]的值，取两者的最⼩值，即为最少货币数。⽤这个⽅法处理第⼆⾏，前两⾏显⽰如下：
⾏
012345678910
\列
50max max max max1max max max max2
20max1max2132432
3
⽤同样的⽅法处理第三⾏，如下：
⾏
012345678910
\列
50max max max max1max max max max2
20max 1max 21324323
max
1
1
2
1
2
2
2
3
2
⾏\列0
12345678910代码：
使⽤python实现上⾯的过程，如下：
import sys
def min_coins(arr, aim):
if arr==None or len(arr)==0 or aim<0:        return -1    n = len(arr)    max = sys.maxsize
dp = [[0]*(aim+1) for i in range(n)]    for j in range(1, aim+1):        dp[0][j] = max
if (j-arr[0])>=0 and dp[0][j-arr[0]]!=max:            dp[0][j] = dp[0][j-arr[0]] + 1    for i in range(1,n):        for j in range(1, aim+1):            temp = max
if (j-arr[i])>=0 and dp[i][j-arr[i]]!=max:                temp = dp[i][j-arr[i]] + 1            dp[i][j] = min(temp, dp[i-1][j])
return dp[n-1][aim] if dp[n-1][aim]!=max else -1
输⼊arr和aim，调⽤上⾯的⽅法查看结果：
arr = [5, 2, 3]aim = 10
res = min_coins(arr, aim)print('换钱的最少货币数为：', res)
结果如下：
换钱的最少货币数为： 2
若要查看dp矩阵的元素，可在输出前打印，或者同最少货币数⼀起返回。
参考：《程序员代码⾯试指南》左程云

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。