动态规划完全背包之518零钱兑换 II

**动态规划完全背包之518零钱兑换 II**

在前面的文章中，我们已经学习了如何使用动态规划解决完全背包问题。今天我们将继续讨论一个更为复杂的版本，即518 题目中的零钱兑换 II。

###问题描述给定一组硬币面额和目标金额，要求找出最少数量的硬币来实现目标金额。每种硬币只能使用一次。

### 动态规划解决方案我们可以将这个问题转化为一个完全背包问题，每个硬币面额代表一个物品，我们需要找到最少数量的物品来达到总价值（目标金额）。

#### 状态定义* `dp[i]` 表示实现总金额 `i` 的最少硬币数。

#### 递归关系对于每种硬币面额 `j`，我们可以选择使用它来实现总金额 `i-j`。因此，我们有：

dp[i] = min(dp[i], dp[i - j] +1)

dp[0] =0

for i in range(1, target +1):
 for j in coins:
 if i >= j:
 dp[i] = min(dp[i], dp[i - j] +1)

class Solution:
 def change(self, amount: int, coins: List[int]) -> int:
 # 初始化状态 dp = [float('inf')] * (amount +1)
 dp[0] =0 # 递归关系的实现 for i in range(1, amount +1):
 for j in coins:
 if i >= j:
 dp[i] = min(dp[i], dp[i - j] +1)
 return dp[amount]