[LeetCode] 322. Coin Change_Medium tag: backpack

﹏ヽ暗。殇╰゛Y 2021-11-16 07:14 196阅读 0赞

You are given coins of different denominations and a total amount of money *amount*. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`.

Example 1:

Input: coins = [1, 2, 5], amount = 11
    Output: 3 
    Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
    Output: -1

Note:  
You may assume that you have an infinite number of each kind of coin.

这个题目就是用无限次的01 背包使得target == si'ze of the backpack.

refer: [\[LeetCode\] 系统刷题5\_Dynamic Programming][LeetCode_ _5_Dynamic Programming]

Code:

class Solution:
        def coinChange(self, coins, amount):
            if not coins or amount < 0: return -1
            n = len(coins)
            dp = [[float('inf')] * (amount + 1) for _ in range(n + 1)]
            for i in range(n + 1):
                dp[i][0] = 0
            for i in range(1, n + 1):
                for j in range(1, amount + 1):
                    if j >= coins[i - 1]:
                        dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1)
                    else:
                        dp[i][j] = dp[i - 1][j]
            return dp[n][amount] if dp[n][amount] < float('inf') else -1

可以用滚动数组将space 优化为O(amount)

转载于:https://www.cnblogs.com/Johnsonxiong/p/11141394.html

[LeetCode_ _5_Dynamic Programming]: https://www.cnblogs.com/Johnsonxiong/p/10793639.html

发表评论取消回复

表情：

评论列表（有 0 条评论，196人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 322. Coin Change

Topic Dynamic Programming Description [https://leetcode.com/problems/coin-chan

谁践踏了优雅/ 2022年12月31日 13:20/ 0 赞/ 137 阅读

相关 leetcode 322. Coin Change | 322. 零钱兑换（动态规划）

题目 [https://leetcode.com/problems/coin-change/][https_leetcode.com_problems_coin-chan

向右看齐/ 2022年10月20日 00:55/ 0 赞/ 216 阅读

相关 leetcode 322 Coin Change

You are given coins of different denominations and a total amount of money amount. Write

绝地灬酷狼/ 2022年08月20日 10:30/ 0 赞/ 9 阅读

相关 LeetCode BackPack 背包问题

//从上个月末之后就开始有点浮躁起来，本来计划国庆查漏补缺的，结果网卡光荣的坏了ORZ……无论如何，OFFER现在还没有拿到，即便是拿到了也不该放松学习的状态。Stay Hun

谁借莪１个温暖的怀抱￠/ 2022年06月07日 01:39/ 0 赞/ 127 阅读

相关 LeetCode：322. Coin Change（硬币兑换问题）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

左手的ㄟ右手/ 2022年04月03日 15:54/ 0 赞/ 186 阅读

相关 backpack

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 1 0-1 背包 2 Int main()

深藏阁楼爱情的钟/ 2022年01月10日 01:15/ 0 赞/ 135 阅读

相关 leetcode [322]Coin Change

You are given coins of different denominations and a total amount of money amount. Write

小咪咪/ 2021年12月07日 14:21/ 0 赞/ 236 阅读

相关 [LeetCode] 322. Coin Change_Medium tag: backpack

You are given coins of different denominations and a total amount of money amount. Write

﹏ヽ暗。殇╰゛Y/ 2021年11月16日 07:14/ 0 赞/ 197 阅读

相关 [leetcode]322. Coin Change找零钱

You are given coins of different denominations and a total amount of money amount. Write

待我称王封你为后i/ 2021年11月11日 01:34/ 0 赞/ 468 阅读

相关 LeetCode : 322. Coin Change 凑齐硬币

试题 You are given coins of different denominations and a total amount of money amount.

￡神魔★判官ぃ/ 2021年06月24日 16:11/ 0 赞/ 348 阅读