零钱兑换问题

题目

给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回-1。

思路

https://leetcode-cn.com/problems/coin-change/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-wei-lai-bu-ke/
贪心算法：

1. 想要总硬币数最少，肯定优先用大面值硬币，所以 coins 按从大到小排序；
2. 优先用大硬币凑

伪代码

k = amount // coin
amount = amount - k * coin
count += k

但是这样做，会因为丢到了导致最后无法凑出总额。
比如：coins = [5, 3, 2,]， amount = 9。
按照上述伪代码，就无法凑出总额。正确的硬币数该是5， 2， 2。

这是一个动态规划问题。动态规划问题，思考如何列出正确的状态转移方程？

1. 确定base case。目标金额为0时，算法返回0，因为不需要任何coin就能凑出目标金额；
2. 确定状态，也就是原问题和子问题中会变化的变量。coin的数量是无限多的，面额也是给定的，因此唯一的状态就是目标金额amount；
3. 确定选择，也就会导致状态产生变化的行为。目标金额为什么变化？因为选择coin，每选择一枚coin，就相当于减少了目标金额。所以说所有的coins，就是选择；
4. 明确dp函数的定义。参数就是状态，函数计算出的结果就是题目要求-凑出目标金额所需的最少硬币数量。

伪代码框架

def coinChange(coins, amount):
    # 定义：要凑出金额n，至少要dp(n)个硬币
    def dp(n):
        # 做选择，选择需要硬币最少的那个结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res
    # 题目要求的最终结果是dp(amount)
    return dp(amount)

上述伪代码，加入base case即可得到最终答案。

def coinChange(coins: List[int], amount: int):
    def dp(n):
        # base case
        if n == 0: return 0
        if n < 0: return -1
        # 求最小值，所以初始化为正无穷
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            # 子问题无解，跳过
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        return res if res != float('INF') else -1
    return dp(amount)

通过备忘录消除子问题

def coinChange(coins: List[int], amount: int):
    # 备忘录
    memo = dict()
    def dp(n):
        # 查备忘录，避免重复计算
        if n in memo: return memo[n]
        # base case
        if n == 0: return 0
        if n < 0: return -1
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        # 记入备忘录
        memo[n] = res if res != float('INF') else -1
        return memo[n]
    return dp(amount)

def coinChange(coins: List[int], amount: int):
    # 备忘录
    memo = dict()
    def dp(n):
        # 查备忘录，避免重复计算
        if n in memo: return memo[n]
        # base case
        if n == 0: return 0
        if n < 0: return -1
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        # 记入备忘录
        memo[n] = res if res != float('INF') else -1
        return memo[n]
    return dp(amount)

零钱兑换 II

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] += dp[x - coin]
        return dp[amount]