Python中的硬币更改
假设我们有不同面额的硬币和总金额。我们必须定义一个函数来计算组成该数量所需的最少数量的硬币。如果硬币的任何组合都无法容纳该金额，请返回-1。因此，如果输入为[1,2,5]，且数量为11，则输出为3。这是使用5+5+1=11形成的。
为了解决这个问题，我们将遵循以下步骤-
如果数量=0，则返回0
如果最小的硬币数组>数量，则返回-1
定义一个称为dp的数组，大小为+1，并用-1填充
对于我在范围硬币阵列
如果dp[j–1]=-1，则跳过下一部分，进行下一次迭代
否则，如果dp[j]=-1，则dp[j]：=dp[j-i]+1
否则dp[j]：=dp[j]和dp[j–i]的最小值+1
如果i>dp的长度–1，则跳过下一部分，进行下一次迭代
dp[i]：=1
对于范围i+1中的j等于
返回dp[金额]
示例
让我们看下面的实现以更好地理解-
class Solution(object):
def coinChange(self, coins, amount):
if amount == 0 :
return 0
if min(coins) > amount:
return -1
dp = [-1 for i in range(0, amount + 1)]
for i in coins:
if i > len(dp) - 1:
continue
dp[i] = 1
for j in range(i + 1, amount + 1):
if dp[j - i] == -1:
continue
elif dp[j] == -1:
dp[j] = dp[j - i] + 1
else:
dp[j] = min(dp[j], dp[j - i] + 1)
#print(dp)
return dp[amount]
ob1 = Solution()print(ob1.coinChange([1,2,5], 11))输入项
[1,2,5] 11
输出结果
3