动态规划实战：零钱兑换与爬楼梯中的组合数与排列数

518. 零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例

• 输入：amount = 5, coins = [1, 2, 5]

• 输出：4

• 解释：有四种方式可以凑成总金额：

  • 5=5
  • 5=2+2+1
  • 5=2+1+1+1
  • 5=1+1+1+1+1

• 输入：amount = 3, coins = [2]

• 输出：0

• 解释：只用面额 2 的硬币不能凑成总金额 3。

• 输入：amount = 10, coins = [10]

• 输出：1

约束条件

• 0 <= amount (总金额) <= 5000
• 1 <= coin (硬币面额) <= 5000
• 硬币种类不超过 500 种
• 结果符合 32 位符号整数

public int change(int amount, int[] coins) {
    // dp[i] 表示凑成金额 i 的组合数
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    
    // 外层循环遍历硬币（物品）
    for (int i = 0; i < coins.length; i++) {
        // 内层循环遍历金额（背包容量），正序遍历
        for (int j = coins[i]; j <= amount; j++) {
            // 状态转移：使用当前硬币 coins[i] 的组合数
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

解题思路

dp 数组代表装满背包的方式种类。初始化 dp[0] 设定为 1，这是后续递推的基础。递推公式如下：dp[j] += dp[j - coins[i]]。

这是一个完全背包问题：硬币可以无限使用 → 完全背包求组合数 → 计数类 DP。

：这里求的是（不考虑顺序），不是排列。