要解决这个统计硬币数量为偶数的组合数问题，我们需要在原有动态规划的基础上，增加一个状态维度来跟踪当前组合的硬币数量奇偶性，而不是修改原有的金额参数。

状态定义 #

我们定义两个二维状态数组：

• even[m][n]：使用前m种硬币凑出金额n，且硬币总数为偶数的组合方式数。
• odd[m][n]：使用前m种硬币凑出金额n，且硬币总数为奇数的组合方式数。

递推关系 #

和原问题的拆分逻辑一致，我们依然将问题分为「不使用第m种硬币」和「至少使用一次第m种硬币」两个子问题，但需要结合奇偶性的翻转规则：

1. 不使用第m种硬币的情况 #

此时组合的硬币数量奇偶性不变，直接继承前m-1种硬币的结果：

even[m][n] += even[m-1][n]
odd[m][n] += odd[m-1][n]

2. 至少使用一次第m种硬币的情况 #

当我们加入一个第m种硬币时，硬币总数的奇偶性会翻转：

• 如果凑出n - S[m-1]的组合是偶数个硬币，加一个硬币后变成奇数，所以要加到odd[m][n]中；
• 如果凑出n - S[m-1]的组合是奇数个硬币，加一个硬币后变成偶数，所以要加到even[m][n]中。

递推公式为：

even[m][n] += odd[m][n - S[m-1]]  // 加一个硬币，奇数变偶数
odd[m][n] += even[m][n - S[m-1]]  // 加一个硬币，偶数变奇数

基例条件 #

• 当金额n = 0时：空组合的硬币数量为0（偶数），所以even[m][0] = 1，odd[m][0] = 0（对任意m成立）。
• 当金额n < 0时：无法凑出，所以even[m][n] = 0，odd[m][n] = 0。
• 当硬币种类m = 0且n ≥ 1时：没有硬币可用，所以even[0][n] = 0，odd[0][n] = 0。

示例验证（N=4，S={1,2,3}） #

我们一步步计算最终的even[3][4]：

1. 仅使用硬币1：
   • even[1][4] = 1（4个1，偶数），odd[1][4] = 0
2. 加入硬币2：
   • even[2][4] = even[1][4] + odd[2][2] = 1 + 1 = 2（对应组合：4个1、2个2）
   • odd[2][4] = odd[1][4] + even[2][2] = 0 + 1 = 1（对应组合：2个1+1个2）
3. 加入硬币3：
   • even[3][4] = even[2][4] + odd[3][1] = 2 + 1 = 3（对应组合：4个1、2个2、1个1+1个3）
     这和你给出的预期结果完全一致。

为什么你的之前尝试无效？ #

你之前修改的是金额参数（比如2*n、n-2*S[m-1]），但问题的约束是硬币数量的奇偶性，和金额翻倍没有直接关系——比如组合1+3的金额是4，硬币数量是2（偶数），但金额并不是任何硬币面额的2倍。因此，必须通过新增状态维度来跟踪奇偶性，而不是修改金额。

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