LeetCode.518.零钱兑换 II（中等）

题目

LeetCode.518.零钱兑换 II（中等）

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

题解

划分子问题
设dp[i]为凑成总金额i的硬币组合数。
假设coins = [1, 2, 5]，那么dp[i]其实就是硬币总额i - 1、i - 2、i - 5子问题之和。

状态转移方程
for (coin: coins) dp[i] += dp[i - coin]

注意点
所求的是硬币的组合数，不是排列数。
比如coins = [1, 2]，amount = 3，1 + 2和2 + 1是同一种组合，但是两个排列。
如果我们是先确定一个amount，再去用所有硬币去凑，就会凑出来不同的排列。
所以要锁定硬币使用的顺序，同一个金额下就不会有不同顺序的硬币的使用情况了。

class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val dp = IntArray(amount + 1) { 0 }
        dp[0] = 1
        for (coin in coins) {
            for (a in coin..amount) {
                dp[a] += dp[a - coin]
            }
        }
        return dp[amount]
    }
}