动态规划求解硬币兑换问题变体：等额硬币数拆分计数

首先得明确问题核心：给定面额集合 S = [1, 2, 6, 12, 24, 48, 60]，我们要计算将金额 n 拆分为A、B两部分的不同方式数，要求A、B各自用S中的硬币凑出的硬币数量完全相同。比如n=6时最终结果是4种，我们后面会手动验证这个例子。

思路拆解 #

可以把问题拆成两个递进的部分：

1. 先计算「用恰好k枚硬币凑出金额m」的方式数，记为 dp[k][m]。
2. 对每个可能的硬币数量k，统计A用k枚凑x、B用k枚凑n-x的组合总数，最后把所有k对应的总数累加，就是最终答案。

动态规划定义与转移 #

1. 初始化DP数组

• dp[k][m] 表示用恰好k枚硬币凑出金额m的方式数。
• 初始状态：
  • dp[0][0] = 1：0枚硬币凑0金额，只有1种方式（什么都不拿）。
  • 所有 dp[0][m>0] = 0：0枚硬币不可能凑出正金额。
  • 所有 dp[k>0][0] = 0：正数量的硬币不可能凑出0金额。

2. 状态转移方程

对于每种硬币面额 c，我们遍历硬币数量k（从1到最大可能值，最大就是n——毕竟用1元硬币最多需要n枚），再遍历金额m（从c到n）：

dp[k][m] += dp[k-1][m - c]

这个逻辑很直观：要凑出m金额用k枚硬币，我们可以先拿1枚面额c的硬币，剩下的k-1枚硬币凑出m-c的金额，把所有这种情况的方式数加起来即可。

计算最终答案 #

对于每个k（从1到max_k，max_k取n即可），我们需要计算所有x从0到n的dp[k][x] * dp[k][n-x]的总和——这代表A用k枚凑x、B用k枚凑n-x的组合数，把每个k的这个总和加起来就是最终的拆分方式数。

验证示例n=6 #

我们手动计算验证：

• k=1：dp[1][x]仅当x是S中的面额时为1（1、2、6）。对应n-x为5、4、0，这些金额用1枚硬币都凑不出来，所以k=1贡献0。
• k=2：dp[2][x]的有效值为：
  • x=2（1+1）→1种；x=3（1+2）→1种；x=4（2+2）→1种
    计算总和：dp[2][2]*dp[2][4] + dp[2][3]*dp[2][3] + dp[2][4]*dp[2][2] = 1*1 + 1*1 +1*1 =3
• k=3：dp[3][x]的有效值为：
  • x=3（1+1+1）→1种；x=6（2+2+2）→1种
    总和：dp[3][3]*dp[3][3] =1*1=1（其他x对应的n-x无法用3枚硬币凑出）
• k≥4：4枚硬币最少凑4元，n-x=6-4=2，无法用4枚硬币凑出，贡献0。

总方式数=0+3+1=4，完全符合示例结果。

代码实现（Python） #

如果要写代码实现这个逻辑，可以参考下面的片段：

def count_split_ways(n, S):
    max_k = n  # 最多用n枚1元硬币
    # 初始化DP数组：dp[k][m]，k从0到max_k，m从0到n
    dp = [[0]*(n+1) for _ in range(max_k+1)]
    dp[0][0] = 1
    
    for c in S:
        # 无限硬币场景：先遍历硬币，再遍历硬币数量，最后遍历金额
        for k in range(1, max_k+1):
            for m in range(c, n+1):
                dp[k][m] += dp[k-1][m - c]
    
    ans = 0
    for k in range(1, max_k+1):
        total = 0
        for x in range(0, n+1):
            if n - x >=0:
                total += dp[k][x] * dp[k][n -x]
        ans += total
    return ans

# 测试示例
S = [1,2,6,12,24,48,60]
print(count_split_ways(6, S))  # 输出4，正确

优化思路 #

如果n很大，上面的O(max_k * n * |S|)复杂度可能有点高。我们可以优化计算每个k的sum(dp[k][x] * dp[k][n-x])：这其实是数组dp[k]的自卷积在n处的值，可以用FFT加速计算，但对于一般规模的n，上面的基础DP已经足够用了。

内容的提问来源于stack exchange，提问作者Eduardo J. Sanchez