零钱兑换问题

零钱兑换问题是一个经典的动态规划问题，其核心在于通过组合不同面额的硬币，找到组成目标金额所需的最小硬币数量。以下是针对该问题的详细解答：

核心思路

动态规划：将问题分解为子问题，通过存储子问题的解来避免重复计算。
完全背包问题：每种硬币可以无限使用，因此这是一个完全背包问题。

算法步骤

初始化：
创建一个数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币数。
初始化 dp[0] = 0，因为凑成0元需要0个硬币。
对于其他金额，初始化为一个很大的值（如 float('inf')），表示不可达。
去重并排序：
对硬币数组进行去重并排序，以避免重复计算和优化遍历顺序。
动态规划填充：
遍历从1到目标金额的所有可能金额。
对于每个金额，遍历所有硬币面额。
如果当前硬币面额小于等于当前金额，则更新 dp[amount] 为 min(dp[amount], dp[amount - coin] + 1)。
返回结果：
如果 dp[target_amount] 仍然是初始的大值，说明无法组成目标金额，返回-1。
否则，返回 dp[target_amount]。

代码实现def coinChange_optimized(coins, target_amount): # 去重并排序 coins = sorted(set(coins)) dp = [float('inf')] * (target_amount + 1) dp[0] = 0 for amount in range(1, target_amount + 1): for coin in coins: if coin <= amount: dp[amount] = min(dp[amount], dp[amount - coin] + 1) return dp[target_amount] if dp[target_amount] != float('inf') else -1复杂度分析

时间复杂度：O(n * m)，其中 n 是目标金额，m 是硬币的种类数。
空间复杂度：O(n)，用于存储 dp 数组。

示例

假设硬币面额为 [1, 2, 5]，目标金额为 11：

dp[0] = 0
dp[1] = min(inf, dp[0] + 1) = 1
dp[2] = min(inf, dp[1] + 1, dp[0] + 1) = 1
dp[5] = min(inf, dp[4] + 1, dp[3] + 1, dp[0] + 1) = 1
dp[11] = min(inf, dp[10] + 1, dp[9] + 1, dp[6] + 1) = 3（使用两个5和一个1）

最终结果为 3。

注意事项

硬币去重：避免重复计算相同面额的硬币。
排序：虽然不是必须的，但排序可以优化遍历顺序。
初始值：使用 float('inf') 表示初始不可达状态。

通过动态规划的方法，可以高效地解决零钱兑换问题，找到组成目标金额的最小硬币数量。

您可能感兴趣问答

Collapsible

热门标签

热点问答