0322. 零钱兑换 #

标签：动态规划
难度：中等

题目大意 #

给定不同面额的硬币 coins 和一个总金额 amount。求出凑成总金额所需的最少的硬币个数。如果无法凑出，则返回 -1。

解题思路 #

完全背包问题。

可以转换为有 n 枚不同的硬币，每种硬币可以无限次使用。凑成总金额为 amount 的背包，最少需要多少硬币。

动态规划的状态 dp[i] 可以表示为：凑成总金额为 i 的组合中，至少有 dp[i] 枚硬币。

动态规划的状态转移方程为：dp[i] = min(dp[i], + dp[i-coin] + 1，意思为凑成总金额为 i 最少硬币数量 = 「不使用当前 coin，只使用之前硬币凑成金额 i 的最少硬币数量」和「凑成金额 i-num 的最少硬币数量，再加上当前硬币」两者的较小值。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf') for _ in range(amount + 1)]
        dp[0] = 0

        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)

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