🥈322.零钱兑换@

🥈Medium

给定不同面额的硬币 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

示例 4：

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

示例 5：

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

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <=
• 0 <= amount <=

  题解

  还是不大会，😔，需要好好领会！！

  暴力递归

  首先，这是一个动态规划问题。因为它具有最优子结构。要符合最优子结构，子问题之间必须相互独立。例如，要求amount=11时最少硬币数（原问题），如果知道amount=10的最少硬币数（子问题），只需要把子问题的答案+1（选出一枚面值为1的硬币），就是原问题的答案。因为硬币个数没有限制，所以子问题之间相互独立。

既然知道这是一个动态规划，就要列出正确的动态转移方程。

1.确定base case

很简单，amount=0时，返回0

2.确定状态，也就是原问题和子问题中的变量

由于硬币是无限的，面额是题目给定的，只有目标金额会不断向base case靠近，所以唯一状态就是目标金额amount

3.确定选择，也就是导致状态产生变化的行为

每选择一枚硬币，就减少了目标金额，所以选择就是硬币的面额

4.明确dp函数/数组的定义

很明显，这里的dp函数，需要输入目标金额n，返回凑出目标金额n的最少硬币数。

这样就可以写出大致框架：

根据上面这些关键点，再加上base case，代码就可以写出来了：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 定义：要凑出金额n，至少需要dp(n)枚硬币
        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)

但这样时间复杂度很高，提交也会显示超出时间限制

不过可以根据上面的过程写出状态转移方程：

画出amount=11，``coins=[1,2,5]的递归树如图：

带备忘录的递归

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 定义：要凑出金额n，至少需要dp(n)枚硬币
        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)

dp数组的迭代