python 最小硬币数_[动态规划]最少硬币问题

最少硬币问题是一个经典的动态规划问题，其解法如下：

假设我们有硬币的面值数组为 coins，需要凑出总金额 amount，我们可以定义一个数组 dp，其中 dp[i] 表示凑出金额 i 所需的最少硬币数量。

显然，当 i=0 时，dp[0]=0。

对于其他的金额 i，我们可以枚举硬币的面值 coin，如果 coin<=i，则 dp[i] 的值可以通过 dp[i-coin]+1 来转移，即先凑出 i-coin 元，再加上一枚面值为 coin 的硬币。

最终，dp[amount] 即为凑出总金额 amount 所需的最少硬币数量。

以下是 Python 代码实现：

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

其中，当 dp[amount] 为无穷大时，表示无法凑出总金额 amount，此时返回 -1。

相关问题

硬币问题动态规划

硬币问题是一个著名的动态规划问题，其描述为：给定不同面额的硬币和一个总金额，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

例如，假设有三种面值的硬币，分别为1元、2元、5元，需要凑成11元，那么最少需要的硬币数为3枚（5元+5元+1元）。

解决这个问题的一种常见方法是使用动态规划。具体来说，我们定义一个长度为amount+1的数组dp，其中dp[i]表示凑成金额i所需的最少硬币个数。初始时，dp[0]=0，表示凑成金额0不需要任何硬币。对于每个金额i，我们遍历所有的硬币面值j，如果j<=i，则可以使用一枚面值为j的硬币，将问题转化为求解凑成金额i-j所需的最少硬币个数，即dp[i-j]+1。我们只需要选择所有方案中最小的那个作为dp[i]的值即可。

最终，dp[amount]就是所求的答案。

下面是一个使用Python实现的动态规划算法：

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for j in coins:
            if j <= i:
                dp[i] = min(dp[i], dp[i - j] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

在上面的代码中，coins表示硬币面值列表，amount表示需要凑成的金额。我们首先初始化dp数组，将所有元素设置为正无穷，然后将dp[0]设为0。接下来，我们遍历所有的金额i，对于每个金额i，再遍历所有的硬币面值j，如果j<=i，则更新dp[i]的值为dp[i-j]+1和dp[i]中的较小值。最后返回dp[amount]的值，如果它仍然是正无穷，则说明无法凑成金额amount，返回-1即可。

编写一个基于动态规划算法的找零函数，用coin硬币体系找零M，找到所需硬币数最小的找零方式

编写一个基于动态规划的找零函数，可以用来解决经典的“最少硬币找零”问题。这个算法通常用于处理给定一组不同面额的硬币和总金额M，如何组合这些硬币使得找零所需的硬币数目最少。

假设我们有硬币数组`coins[]`，包含每个面额，例如`[1, 5, 10]`代表有1元、5元和10元三种硬币。我们可以使用动态规划的方法定义状态`dp[i]`表示找到i元零钱所需的最小硬币数。

算法步骤如下：

1. 初始化一个长度为`M+1`的数组`dp`，所有元素设为无穷大（或者初始值设为0），除了`dp[0]`设为0，因为不需要任何硬币就可以得到0元。
2. 遍历硬币数组`coins`，对于每个硬币`coin`：
a. 计算当前状态`i`下，使用该硬币后的状态，即`dp[i - coin] + 1`，如果这比之前的`dp[i]`小，则更新`dp[i]`为新的值。
3. 最终，`dp[M]`就是找零M元所需要的最小硬币数。

Python示例代码：

def min_coins(coins, M):
    dp = [float('inf')] * (M + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, M + 1):  # 将coin从最大到0遍历
            if dp[i - coin] != float('inf'):  # 如果前面的状态有效
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[M] if dp[M] < float('inf') else None

# 使用示例
coins = [1, 5, 10]
M = 11
print(min_coins(coins, M))  # 输出：3 (10+1=11, 或者 5+5+1=11)