IT 面试题库

LeetCode 322 零钱兑换:用给定面额 coins 凑出金额 amount,求最少硬币数。说明这是哪种背包模型及转移。

中级编程题算法工程师Java后端工程师动态规划完全背包零钱兑换

题目

考察点:完全背包(硬币可无限用)的最值模型,以及『初始化无穷大』的细节与遍历方向。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 65 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

思路:这是『完全背包』求最小值的经典题——每种硬币可用无限次,目标凑出 amount 且硬币数最少。

要点(状态与转移):

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for c in coins:
        for j in range(c, amount + 1):
            dp[j] = min(dp[j], dp[j - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

要点(注意):

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题