518. 零钱兑换 II - Kotlin 背包DP

原题地址：https://leetcode.cn/problems/coin-change-ii/description/

题解

反向题目：377. 组合总和 Ⅳ

对于背包问题而言

• 外层遍历背包，内层遍历物品，最终结果为排列情况
• 外层遍历物品，内层遍历背包，最终结果为组合情况

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val dp = IntArray(amount + 1) { 0 }
        coins.forEach { coin ->
            dp.forEachIndexed { i, _ ->
                if (i == 0) dp[i] = 1 else if (i - coin >= 0) dp[i] += dp[i - coin]
            }
        }
        return dp[amount]
    }
}