题目

LeetCode.322.零钱兑换（中等）

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

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

题解

一组东西中进行多种选择最终达到一个目标值，联想到背包问题，尝试划分子问题。

得到amount的上一步一定是从coins选择一个硬币得来的，但是不知道哪种选择所需的硬币数最少，那么就每个都试一下，取硬币数最少的。

选取一个硬币coin后，剩下amout - coin的金额是怎么得来的，也是同样的选择过程，并且这个子问题加上新的选择过程得到最优的最终结果，符合最优子结构。

如果一直选择先去有可能发现不能用选择过的硬币累加成amount，那就是无法组合。

如果一直选下去，发现可以凑成amount，记录选择过的硬币数量，同时每次对比最终取一个最少的硬币数量。

递归

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        fun select(amount: Int): Int {
            if (amount < 0) return -1
            if (amount == 0) return 0
            var minCount = Int.MAX_VALUE
            for (coin in coins) {
                val count = select(amount - coin)
                if (count == -1) continue
                minCount = minOf(minCount, 1 + count)
            }
            return if (minCount == Int.MAX_VALUE) -1 else minCount
        }
        return select(amount)
    }
}

重叠子问题
画出递归树，会发现会有重叠子问题，有大量的重复计算。
例如coins = [1,2,4]。
四次select(amount - 1)跟一次select(amount - 4)是重复计算的。
两次select(amount - 2)跟一次select(amount - 4)是重复计算的。

记忆化递归
消除重叠子问题就是记录中间计算结果。
计算的结果是硬币数，中间状态是跟amount有关，但是并不是0到amount都会有计算结果，所以可以用哈希表来存储中间状态，节省一点空间。

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        val memo = mutableMapOf<Int, Int>()
        fun select(amount: Int): Int {
            if (amount < 0) return -1
            if (amount == 0) return 0
            if (memo[amount] != null) memo[amount]!!
            var minCount = Int.MAX_VALUE
            for (coin in coins) {
                val count = select(amount - coin)
                if (count == -1) continue
                minCount = minOf(minCount, 1 + count)
            }
            val result = if (minCount == Int.MAX_VALUE) -1 else minCount
            memo[amount] = result
            return result
        }
        return select(amount)
    }
}

自底向上动态规划

记忆化递归从大的amount往小的amount去算，也可以从小的amount去递推大的amount。
初始值dp[0] = 0要存储一下。

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        val dp = mutableMapOf<Int, Int>()
        dp[0] = 0
        for (a in 1..amount) {
            var minCount = Int.MAX_VALUE
            for (coin in coins) {
                val count = dp.getOrDefault(a - coin, -1)
                if (count == -1) continue
                minCount = minOf(minCount, count + 1)
            }
            dp[a] = if (minCount == Int.MAX_VALUE) -1 else minCount
        } 
        return dp[amount]!!
    }
}