类有限硬币找零变种：区间取值硬币目标和排列数求解问题

解法1：动态规划（适合x较小的场景） #

该问题本质是带上限的有序整数拆分计数，因为硬币顺序固定（不同位置硬币取值互换算不同排列），可以通过逐枚硬币递推计算：

• 状态定义：dp[i][s]表示考虑前i枚硬币，总和为s的合法排列数
• 初始状态：dp[0][0] = 1，0枚硬币总和为0仅1种方案
• 递推逻辑：第i枚硬币上限为c[i]，则dp[i][s] = sum_{k=0}^{min(c[i], s)} dp[i-1][s-k]，可以通过前缀和优化将单次递推时间从O(x*c[i])降到O(x)
• 最终结果为dp[n][x]

可优化为一维滚动数组实现，Python示例代码如下：

def count_arrangements(c, x):
    dp = [0] * (x + 1)
    dp[0] = 1
    for ci in c:
        # 前缀和优化加速区间求和
        pre_sum = [0] * (x + 2)
        for s in range(x + 1):
            pre_sum[s + 1] = pre_sum[s] + dp[s]
        new_dp = [0] * (x + 1)
        for s in range(x + 1):
            left = max(0, s - ci)
            new_dp[s] = pre_sum[s + 1] - pre_sum[left]
        dp = new_dp
    return dp[x]

测试验证：count_arrangements([2,2],3)输出2，count_arrangements([3,3,3],4)输出12，和你给出的示例结果完全一致。

解法2：容斥原理闭式公式（适合n较小的场景） #

如果没有上限约束，总和为x的非负整数有序解数量为隔板法结论C(x + n - 1, n - 1)，加入上限约束后通过容斥减去非法情况即可得到结果：

f(x) = sum_{mask=0}^{2^n -1} (-1)^{count(mask)} * C( x - sum_{i in mask} (c_i + 1) + n - 1, n - 1 )
其中：

• count(mask)为mask二进制位中1的个数
• 当x - sum_{i in mask} (c_i + 1) < 0时，对应组合数取0

公式逻辑：mask代表强制违反上限的硬币集合，每个违反上限的硬币i至少取c_i+1，剩余部分用无约束隔板法计算，通过容斥正负号抵消重复扣除的情况。
可直接验证你给出的边界场景：

• x=0时仅mask=0有贡献，C(0 + n - 1, n -1) = 1，符合边界结论
• x=1时仅mask=0有贡献，C(1 + n - 1, n -1) = n，符合边界结论
• 3枚上限为3的硬币求x=4时，计算得C(6,2) - 3*C(2,2) = 15-3=12，和示例结果一致

内容的提问来源于stack exchange，提问作者maskos2000