518. 零钱兑换 II(Medium)

题目描述

给定不同面额的硬币和一个总金额。求出可以凑成总金额的硬币组合数。

样例

Input: amount = 5, coins = [1, 2, 5]
Output: 4
# 所有可能的解
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

题解

本题也是使用动态规划的方法去做，但是本题与其他题目的难点在于，需要求出的是硬币的组合数。而组合数就可能存在重复元素。

很容易写出动态规划的转移方程 dp[5] += dp[5 - 1] + dp[5 - 2] + dp[5 -3]。初始的状态为 dp[1] = dp[2] = dp[5]。

但是在写循环的时候，犯了错误，可以先看我写的代码

func change(amount int, coins []int) int {
    n := len(coins)
    if amount <= 0 {
        return 1
    }
    if n < 1 {
        return 0
    }

    dp := make([]int, amount + 1)
    for _, coin := range coins {
        dp[coin] = 1
    }
    for _, coin := range coins {
        for i := 0; i < amount + 1; i++ {
            if i - coin >= 0 {
                dp[i] += dp[i - coin]
            }
        }
    }
    return dp[amount]
}

乍看一眼，没有问题。但是我们自己手动计算后发现会存在重复组合。 $$ dp[0] = 0 \ dp[1] = dp[1], 情况有 [1] \ dp[2] = dp[2] + dp[1], 情况有 [1, 1], [2] \ dp[3] = dp[2] + dp[1], 情况有 [1, 2], [1, 1, 1], [2, 1] \ $$ 我们发现，这样的话，[1, 2] 和 [2, 1] 组合是重复了，这样的 动态规划 方程在求 可达性 的问题上，其实没有问题，但是对于求 组合问题 会产生重复情况。

那么怎么改进，需要在循环的时候，对于coins 递增选取，即不会存在 [2, 1] 的情况。

那么对于初始条件，我们也不能 dp[1] = dp[2] = dp[5]，因为这个没有保证递增性。所以改成 dp[0]

代码

func change(amount int, coins []int) int {
    n := len(coins)
    if amount <= 0 { // 特例
        return 1
    }
    if n < 1 {
        return 0
    }

    dp := make([]int, amount + 1)
    dp[0] = 1

    for _, coin := range coins { // 保证了 coin 始终是按序取值
        for i := 0; i < amount + 1; i++ {
            if i - coin >= 0 {
                dp[i] += dp[i - coin]
            }
        }
    }
    return dp[amount]
}