322. 零钱兑换（中）

• 题目
• 法一、动态规划
• 法二、带备忘录的动态规划
• 法三、dp数组的迭代解法

题目

• 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
  计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
  你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

法一、动态规划

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> 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)#subproblem 的值加上 1（表示选择了当前硬币）得到当前情况下的硬币数量，并将其与 res 比较，更新 res 为较小的值。
            return res if res!=float('INF') else -1
        return dp(amount)

法二、带备忘录的动态规划

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        memo = []  # 备忘录

        def dp(n):
            if n in memo:  # 如果已经计算过，直接返回结果
                return memo[n]
            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)

法三、dp数组的迭代解法

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 创建一个数组来保存中间结果
        dp = [float('inf')] * (amount + 1)
        # base case
        dp[0] = 0

        # 自底向上迭代
        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], 1 + dp[i - coin])

        return dp[amount] if dp[amount] != float('inf') else -1