最少硬币找零问题（Minimum Coin Change）的变种：恰好组成金额的最少硬币数，且限制每种硬币的使用次数

题目描述
给定一个硬币数组 coins，其中每个硬币有一个面值和一个最大使用次数（即每种硬币最多能使用几次）。再给定一个目标金额 amount。要求计算出用这些硬币恰好组成金额 amount 的最少硬币数量。如果无法组成，返回 -1。

例如：
输入：coins = [1, 2, 5], 每种硬币的最大使用次数 = [3, 2, 1], amount = 11
解释：面值1的硬币最多用3次，面值2的硬币最多用2次，面值5的硬币最多用1次。
一种可能方案：5（1枚） + 2 + 2 + 1 + 1 = 11，共使用5枚硬币。
输出：5

解题思路
这是一个带数量限制的完全背包问题。我们可以把它看作是在标准“最少硬币找零”动态规划的基础上，为每种硬币增加了一个使用次数的上限。

1. 状态定义
   dp[x] 表示凑出金额 x 所需要的最少硬币数。
   初始化时，dp[0] = 0（凑出0元不需要硬币），其余金额设为 INF（一个很大的数，表示不可达）。

2. 状态转移
   对于每一种硬币 coins[i]，其最多使用 limit[i] 次。
   在更新 dp 时，我们不能直接用完全背包的思路（顺序更新），因为那样可能会超出该硬币的限用次数。
   我们需要用分组背包的思想：

   • 把同一种硬币的多个使用次数看作一组物品，这组物品中有 limit[i] 个选择（用1枚、2枚、…、limit[i] 枚），每个选择的“重量”是 k * coins[i]，“价值”是 k 枚硬币（即硬币数量增加 k）。
   • 然后对这组物品，用0-1背包的方法（逆序更新）来更新 dp，确保同组物品不重复使用。

3. 具体步骤
   对每种硬币 i：
   （1）枚举该硬币使用的数量 k 从 1 到 limit[i]。
   （2）对每个 k，计算当前硬币组合的金额 w = k * coins[i] 和硬币数 c = k。
   （3）用 0-1 背包的思路更新 dp：
   从 amount 到 w 逆序更新：dp[j] = min(dp[j], dp[j - w] + c)。

4. 最终结果
   如果 dp[amount] 仍然是 INF，则返回 -1，否则返回 dp[amount]。

举例讲解
以 coins = [1, 2, 5], limits = [3, 2, 1], amount = 11 为例。

1. 初始化：dp[0] = 0，其余为 INF。
2. 处理硬币1（最多用3枚）：
   • k=1：w=1, c=1。从11到1逆序更新：dp[1] = min(INF, dp[0]+1) = 1。
     dp[2] = min(INF, dp[1]+1) = 2，dp[3] = 3，…，dp[11] 会变成 11（用11枚1元硬币，但受限于最多3枚，后续会更新）。
   • 但注意：我们是在“逆序更新”同一个数组，为了避免在同一个硬币上重复使用，必须对每个k都独立计算。
     正确的做法是：在考虑硬币i时，用一个新的临时数组或直接在原数组上逆序遍历，确保不会在同一种硬币上重复累加。
     实际操作中，我们通常用“分组背包”模板：

     for 每种硬币i:
         for 当前硬币使用数量k from 1 to limit[i]:
             for 金额j from amount down to k*coins[i]:
                 dp[j] = min(dp[j], dp[j - k*coins[i]] + k)
     

     但注意：这样会重复计算同一硬币的不同k组合（如k=1和k=2可能被重复使用），所以更安全的方法是二进制优化（见后文）。
3. 处理硬币2（最多2枚）：
   类似，但注意要避免和硬币1的组合冲突。
4. 处理硬币5（最多1枚）：
   同样用逆序更新。
5. 最终 dp[11] 会在比较中取得最小值 5。

优化：二进制拆分
当某种硬币最多使用次数较大时，直接枚举k会超时。
我们可以用二进制拆分把同一种硬币的多个使用次数拆成若干组，每组代表“用 1枚、2枚、4枚、… 这种硬币”的组合，然后对这些组用0-1背包更新。
例如：某种硬币最多用 13 次，可以拆成 1, 2, 4, 6（6=13-1-2-4）四组，这四组的任意组合能表示1~13的任何数量，且每组只选一次。
这样就把 O(limit) 的时间降为 O(log limit)。

伪代码

function minCoinsWithLimit(coins, limits, amount):
    dp = array of size (amount+1) filled with INF
    dp[0] = 0
    for i from 0 to len(coins)-1:
        // 二进制拆分
        cnt = limits[i]
        k = 1
        while cnt > 0:
            use = min(k, cnt)  // 当前组的硬币数
            w = use * coins[i] // 当前组的总面值
            c = use            // 当前组的硬币数
            for j from amount down to w:
                dp[j] = min(dp[j], dp[j - w] + c)
            cnt -= use
            k *= 2
    return dp[amount] if dp[amount] != INF else -1

复杂度分析

• 时间复杂度：O(amount * Σ log(limit[i]))，其中 Σ log(limit[i]) 是所有硬币二进制拆分组数的总和。
• 空间复杂度：O(amount)。

关键点

1. 这是一个“带数量限制的完全背包”，用分组背包+二进制优化。
2. 更新时必须逆序，确保同一种硬币的不同组不会重复使用。
3. 初始化时只有 dp[0] = 0，其余为 INF，表示“恰好”组成金额。