LeetCode Coin Change II：两种DP初始化方式的差异分析

问题背景 #

给定不同面额的硬币数组coins和总金额amount，返回组成该金额的组合数（每种硬币可无限使用，无法组成则返回0）。

正确解法代码 #

public int change(int amount, int[] coins) {
    int max = amount + 1;
    int[] dp = new int[max];

    // 正确初始化
    dp[0] = 1;

    for (int c : coins) {
        for (int i = 1; i < max; i++) {
            if (i - c >= 0) dp[i] += dp[i - c];
        }
    }
    return dp[amount];
}

我的解法代码 #

public int change(int amount, int[] coins) {
    int max = amount + 1;
    int[] dp = new int[max];

    // 我的初始化
    for (int c : coins) {
        if (c <= amount) dp[c] = 1;
    }

    for (int c : coins) {
        for (int i = 1; i < max; i++) {
            if (i - c >= 0) dp[i] += dp[i - c];
        }
    }
    return dp[amount];
}

疑问 #

我认为直接给dp[c]赋值1（表示单枚硬币c可组成金额c）和正确解法中dp[0]=1的效果一致，但实际结果不同，请问我的初始化存在什么问题？两种初始化方式的差异是什么？

问题分析与解答 #

你的初始化存在的核心问题 #

1. 错误生成排列计数而非组合计数
   正确DP的逻辑是按硬币逐个处理，每次只新增包含当前硬币的组合，以此保证组合不考虑顺序（比如1+2和2+1算同一个组合）。而你的初始化提前把所有单枚硬币的组合放入dp数组，后续处理硬币时，会把已有组合（包括其他硬币的组合）和当前硬币叠加，导致把不同顺序的排列当成了不同组合。
   举个例子：coins=[1,2]，amount=3

   • 你的解法步骤：
     1. 初始dp=[0,1,1,0]
     2. 处理硬币1时，i=2会执行dp[2] += dp[1]，让dp[2]变成2（包含1+1和2）——此时还没处理硬币2，就错误地把跨硬币的组合算进去了
     3. 处理硬币2时，i=3执行dp[3] += dp[1]，最终dp[3]变成3，而正确组合数应该是2（1+1+1、1+2）

2. 忽略金额0的边界情况
   当amount=0时，题目要求返回1（空组合），但你的解法中dp[0]始终是0，会返回错误结果。

3. 潜在的重复面额问题
   如果coins中存在重复面额（比如[1,1]），你的初始化会多次给dp[1]赋值1，最终dp[1]还是1，但正确解法会因为重复处理硬币1，导致dp[1]变成2，这也不符合组合数的要求（重复硬币不算新面额）。

两种初始化方式的本质差异 #

• 正确初始化dp[0]=1：
  dp[0]=1是递推的边界条件，代表「组成金额0的组合数为1（空组合）」。当处理硬币c时，对于金额i=c，dp[i] += dp[i-c]等价于新增「只用一枚c硬币」的组合，完全贴合逐步构建组合的逻辑。这种方式保证了按硬币顺序处理时，只会生成不考虑顺序的组合，避免重复计数。

• 你的初始化dp[c]=1：
  直接给单枚硬币对应的金额赋值1，相当于提前把所有「单枚硬币」的组合放入结果，但后续递推会无差别地将这些组合与其他硬币的组合叠加，最终生成的是排列数而非题目要求的组合数，同时完全忽略了金额0的边界情况。

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