程序查找在Python中进行更改所需的硬币数量
假设我们有不同面额的硬币(1,5,10,25)和总金额。我们必须定义一个函数来计算组成该数量所需的最少数量的硬币。因此，如果输入为64，则输出为7。这是使用25+25+10+1+1+1+1=64形成的。
为了解决这个问题，我们将遵循以下步骤-
如果数量=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, amount):
coins = [1,5,10,25]
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)
return dp[amount]
ob1 = Solution()
print(ob1.coinChange(64))输入项
64
输出结果
7