最少硬币找零问题的变种：限制每种硬币最多使用一次，求总金额的最少硬币数

题目描述
假设有不同面额的硬币数组 coins 和一个目标总金额 amount。每种硬币最多只能使用一次（即每种硬币数量为1）。请你计算并返回可以凑成总金额所需的最少硬币个数。如果无法凑出总金额，则返回 -1。

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：使用硬币 5、5、1 可以凑成 11，但这里每种硬币最多使用一次，所以可行组合是 5、2、1（使用硬币5、2、1各一次），共3枚硬币。

示例 2：
输入：coins = [2], amount = 3
输出：-1
解释：无法只用一枚面额为2的硬币凑出3（因为最多用一次），也没有其他硬币可用。

示例 3：
输入：coins = [1, 2, 3, 7], amount = 10
输出：2
解释：使用硬币 7 和 3 即可凑成 10（7+3），共2枚硬币。

解题过程循序渐进讲解

步骤1：理解问题本质
这是经典“最少硬币找零”问题（LeetCode 322）的变种。经典问题中每种硬币数量无限，可以用完全背包思路解决。而本题限制每种硬币最多用一次，相当于每个硬币是一个“物品”，只能选或不选，转化为 0-1背包 问题。但注意目标不是最大价值，而是最少物品（硬币）数量，且要恰好装满背包（总金额 exactly = amount）。

步骤2：定义状态
我们定义动态规划数组 dp[j] 表示：凑出总金额 j 所需的最少硬币数量。

• 初始化：dp[0] = 0（凑出金额0不需要硬币），其他 dp[j] = INF（一个很大的数，表示不可达）。
• 目标：求 dp[amount]，若为 INF 则返回 -1。

步骤3：状态转移方程
因为每种硬币最多用一次，我们需要依次考虑每个硬币，并且为了避免同一硬币被重复使用，在遍历金额 j 时应从大到小遍历（0-1背包的标准技巧）。
对于当前硬币面额 coin，如果选择这枚硬币，则凑金额 j 的最少硬币数 = 凑金额 j - coin 的最少硬币数 + 1。
因此状态转移为：

dp[j] = min(dp[j], dp[j - coin] + 1)  对于每个 coin，j 从 amount 递减到 coin

注意：只有 dp[j - coin] 可达（不为 INF）时，才能转移。

步骤4：详细递推过程
以示例1为例：coins = [1, 2, 5], amount = 11。

1. 初始化 dp[0]=0, dp[1..11]=INF。
2. 考虑硬币 1：
   j 从 11 到 1：
   • j=1: dp[1] = min(INF, dp[0]+1) = 1
   • j=2: dp[2] = min(INF, dp[1]+1) = 2
   • ... 最终 dp[1..11] 都变为 j 本身（因为只用硬币1，需要j枚）。
3. 考虑硬币 2：
   j 从 11 到 2：
   • j=2: dp[2] = min(2, dp[0]+1) = 1
   • j=3: dp[3] = min(3, dp[1]+1) = 2
   • j=4: dp[4] = min(4, dp[2]+1) = 2
   • 继续更新到 j=11，会发现更优解。
4. 考虑硬币 5：
   j 从 11 到 5：
   • j=5: dp[5] = min(3, dp[0]+1) = 1
   • j=6: dp[6] = min(4, dp[1]+1) = 2
   • j=7: dp[7] = min(5, dp[2]+1) = 2
   • j=8: dp[8] = min(4, dp[3]+1) = 3
   • j=9: dp[9] = min(5, dp[4]+1) = 3
   • j=10: dp[10] = min(6, dp[5]+1) = 2
   • j=11: dp[11] = min(7, dp[6]+1) = 3
     最终 dp[11] = 3，即使用硬币5、2、1各一枚。

步骤5：边界情况和初始化

• 如果 amount 为 0，直接返回 0。
• 如果 coins 为空，则无法凑出任何正数金额，返回 -1（除非 amount=0）。
• INF 可以设置为 amount+1 或一个较大数（因为最多硬币数不会超过 amount，假设有面额1的硬币）。

步骤6：复杂度分析
时间复杂度：O(n * amount)，其中 n 是硬币种类数。
空间复杂度：O(amount)，只用一维 dp 数组。

步骤7：最终代码框架（伪代码）

def coinChangeLimited(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for j in range(amount, coin - 1, -1):  # 从大到小遍历
            if dp[j - coin] != INF:
                dp[j] = min(dp[j], dp[j - coin] + 1)
    return dp[amount] if dp[amount] != INF else -1

步骤8：验证与测试

• 测试示例1：coins=[1,2,5], amount=11 → 3 ✅
• 测试示例2：coins=[2], amount=3 → -1 ✅
• 测试示例3：coins=[1,2,3,7], amount=10 → 2 ✅
• 特殊情况：amount=0 → 0 ✅
• 无解情况：coins=[3,4], amount=2 → -1 ✅

总结
这个问题巧妙地将最少硬币问题与0-1背包结合，关键点是：

1. 识别每种硬币最多用一次 → 0-1背包。
2. 目标是最少硬币数 → 状态为最少数量。
3. 遍历金额需从大到小，避免硬币重复使用。
4. 初始化 INF 表示不可达，最终判断是否可达。

通过这个例子，你可以更深入理解0-1背包在最少数量问题上的应用，并与完全背包的硬币找零经典问题对比。