【动态规划6】零钱兑换问题

经过本章节前5道题的练习，大家能体会到动态规划的核心在于： 状态定义 和 状态转移方程。其本质是通过分解问题，将复杂问题拆解为较小的子问题，并用递推关系求解。

1. 状态定义

题目要求是什么，我们就定义什么为状态。

• 本题的目标是求出组成总金额 amount 的最少硬币使用个数，因此可以定义：

  • dp[i] 表示组成金额 i 所需的最少硬币个数。

• 初始化：

  • 对于金额为 0 的情况，不需要任何硬币，因此 dp[0] = 0。
  • 对于其他金额，初始化为无穷大（INT_MAX），表示初始状态无法到达。

2. 状态转移方程

状态转移的核心在于：当前状态依赖于之前的选择。

• 在计算 dp[i] 时，可以考虑最后一步选择了一个面值为 coin 的硬币：

  • 剩余金额变为 i - coin；

  • 对应的状态为 dp[i - coin]。

  • 新状态可以通过公式更新为：

    $$dp[i] = \min(dp[i], dp[i - coin] + 1)$$

    其中，coin 是所有硬币面值中的一种。

• 直观解释：
  对于每一个金额 i，尝试使用所有可能的硬币面值 coin，取这些状态中的最小值并加上当前这一步的硬币个数 +1。

3. 边界条件

• 如果无法组成金额 amount，即 dp[amount] 保持为无穷大，则返回 -1；
• 否则，返回 dp[amount]。

这里塔子哥就不从集合的角度重新分析一遍了。大家可以自己试试按照之前集合划分的步骤来推导出该转移方程。

实现代码

以下是使用 python 实现的代码：

# 读取输入
n = int(input())  # 输入一个整数 n，表示硬币的种类数
coins = list(map(int, input().split()))  # 输入 n 个整数，表示每种硬币的面值
amount = int(input())  # 输入一个整数 amount，表示目标金额

# 初始化动态规划数组
# dp[i] 表示组成金额 i 所需的最少硬币个数
# 初始时，除了 dp[0] = 0，其余都设置为一个较大的数，表示尚未达到
dp = [float('inf')] * (amount + 1)
dp[0] = 0  # 金额为 0 时，不需要任何硬币

# 遍历每一个硬币
for coin in coins:
    # 从当前硬币面值到目标金额进行遍历
    for x in range(coin, amount + 1):
        if dp[x - coin] + 1 < dp[x]:
            dp[x] = dp[x - coin] + 1
            # 解释：
            # 如果使用当前硬币 coin 后，组成金额 x 所需的硬币数比之前记录的 dp[x] 更少，
            # 则更新 dp[x] 为 dp[x - coin] + 1

# 判断并输出结果
if dp[amount] == float('inf'):
    print(-1)  # 如果 dp[amount] 仍为无穷大，表示无法组成该金额
else:
    print(dp[amount])  # 输出组成金额 amount 所需的最少硬币个数

题目描述：

给定一个整数数组 $coins$，其中 $coins[i]$ 表示一个面额为 $coins[i]$ 的硬币；再给定一个整数 $amount$，表示你需要组成的总金额。请你计算组成该金额所需的最少硬币个数。如果没有任何一种硬币组合能够凑成该金额，返回 $-1$。

你可以假设每种硬币无数量限制。

输入

• 一个整数数组 $coins$，长度为 $n$，表示硬币的面额。$1 \leq n \leq 12$，$1 \leq coins[i] \leq 100$。
• 一个整数 $amount$，表示目标金额，满足 $0 \leq amount \leq 5000$。

输出

• 返回组成 $amount$ 的最少硬币个数。如果不能组成该金额，返回 $-1$。

示例

示例 1：

输入：

3
1 2 5
11

输出：

3

解释：通过选择 $5 + 5 + 1$，可以组成 $11$，所以最少需要 3 个硬币。

示例 2：

输入：

1
2
3

输出：

-1

解释：不能通过任何方式凑成 $3$。

提示

• 假设给定的硬币面额是有限的，且每个面额的硬币数量无限。