跳至主要內容

剑指 Offer II 103. 最少的硬币数目

ITCharge大约 1 分钟

剑指 Offer II 103. 最少的硬币数目open in new window

  • 标签:广度优先搜索、数组、动态规划
  • 难度:中等

题目链接

题目大意

给定不同面额的硬币 coins 和一个总金额 amount

乔秋:计算出凑成总金额所需的最少的硬币个数。如果无法凑出,则返回 -1

解题思路

完全背包问题。

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

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

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

代码

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