题目：

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

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

题意解析： 有一堆不同面额的硬币，问最少取多少枚硬币，可以凑够想要的面值。

DFS解析：

Coin Change - LeetCode

  1. 为了最终硬币数量最少，首先对硬币面值从大到小排序
    • 因为面值大的越靠前，最后所需额度也会相应减小，硬币数量也会减少
  2. 构建DFS函数
    • 确定边界，若不存在目标金额，则返回当前最小值
    • 遍历硬币面值： 若存在当前硬币面值小于等于目标金额且目标金额小于边界条件（防止溢出），则drill down，进入下一层循环寻找剩余金额所需硬币
  3. 设置目标金额，遍历硬币面值，求解
def coinChange(self, coins, amount):
    coins.sort(reverse = True)
    coins_len, self.result = len(coins), float(“inf”)
    
    def dfs(index, target, count):
        if not target:
            self.res = min(self.res, count)
        for i in range(index, coins_len):
            if coins[i] <= target < coins[i] * (self.result-count): # if hope still exists
                dfs(i, target-coins[i], count+1)

    for i in range(coins_len):
        dfs(i, amount, 0)
    return self.result if self.result < float(“inf”) else -1

剪枝

上面方式遍历过程中并不需要全部遍历全部结果，可以通过剪枝，去除多余的选项：

  1. 同上对硬币面值排序（从大到小）
  2. 构建countCoins函数：
    • 设置金额上限及硬币上限，若当前金额大于目标金额则返回
    • 求模，针对当前硬币和目标金额取模，若满足条件即表示当前的coin可以将目标金额填满，只需要计算coins即可
    • 遍历目标金额，从大至小，依次递减1： 若存在目标金额与对应面值的硬币匹配的情况（求模），则将硬币记录下来
  3. 针对目标金额遍历求值即可
import math
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse = True)
        coins_len, result = len(coins), amount + 1 

        def countCoins(index, target, count):
            if count + math.ceil(target/coins[index]) >= result:
                return
            
            if target % coins[index] == 0:
                result = count + target//coins[index]
                return 
            
            if index == coins_len - 1:
                return
            for i in range(target//coins[index], -1, -1):
                countCoins(index+1, target - coins[index]*i, count+1)
        
        countCoins(0, amount, 0)
        return -1 if result > amount else result

BFS 解析

Coin Change - LeetCode

  1. 将问题转化为求X轴0点到坐标点amount的最短距离 （每次向前行进的合法距离为coin的面值）
  2. visited = [False]*(amount+1) 构建数组，存放后续遍历的节点
  3. 和DFS类似，先遍历对应硬币的面值 在这个过程中，计算当前硬币面值与已有硬币的和集，比较当前金额和目标金额的差异（相等则返回并记录硬币，超过目标金额则放弃，不处理） 若 当前金额不在已访问过的数组中，则将当前金额添加至已访问过的数组中
  4. 返回遍历后的结果
class Solution(object):
    def coinChange(self, coins, amount):
        if amount == 0:
            return 0
        value1 = [0]
        value2 = []
        nc =  0
        visited = [False]*(amount+1)
        visited[0] = True
        while value1:
            nc += 1
            for v in value1:
                for coin in coins:
                    newval = v + coin
                    if newval == amount:
                        return nc
                    elif newval > amount:
                        continue
                    elif not visited[newval]:
                        visited[newval] = True
                        value2.append(newval)
            value1, value2 = value2, []
        return -1

动态规划解析：

Coin Change - LeetCode

  1. 首先声明一个大小为amount+1的数组dp，用dp[i]存储”对于金额amount最少用到的硬币数coins”
    • 为什么大小是amount+1？比如amount是11块，dp要从0元开始存储到11块，所以数组的大小要amount+1
    • 对于初始化数组dp的索引i=0的元素值为0，是因为0块要的硬币数为0，所以初始化为0
  2. 根据数组dp的定义，得到方程: dp[i] = min(dp[i-coin]+1) 注意：dp[i-coin]的coin是针对每一种硬币
  3. 返回值
    • dp[amount]返回dp数组的最后一个元素，dp[amount] == float(“inf”)返回dp数组最后的元素是否为inf(无穷大)
    • 这里用一个例子解释[3, -1][True]返回的是索引为1的元素，[3, -1][False]返回索引为0的元素
    • 所以dp[amount]不等于inf则返回dp[amount]，等于inf则返回-1，意味着任何一种硬币组合能组成总金额

time: O(amount*len(coins) 第一层循环遍历了amount次，第二层循环遍历了数组coins的每个元素 space: O(amount) 算法用一个大小为amount+1的数组来存储值

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [float(“inf”)] * amount
        for i in range(1, amount + 1):
            dp[i] = min([dp[i - c] if i - c >= 0 else float(“inf”) for c in coins]) + 1

        return [dp[amount], -1][dp[amount] == float(‘inf’)]

如上方式可以转换如下通俗的方式：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:       
        n = len(coins)
        # dp[i]表示金额amount需要的最少coins数
        dp = [float("inf")] * (amount+1)
        dp[0] = 0
        for i in range(amount+1):
            for j in range(n):
                if coins[j] <= i:
                    dp[i] = min(dp[i], dp[i-coins[j]]+1)
 
        return dp[amount] if dp[amount] <= amount else -1
Last Updated: