前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode-Medium 322. Coin Change

Leetcode-Medium 322. Coin Change

作者头像
致Great
发布2019-03-15 10:44:02
7610
发布2019-03-15 10:44:02
举报
文章被收录于专栏:程序生活

题目描述

假设给你不同面额的硬币和一个金额amount。编写一个函数来计算构成该金额amount所需的最少数量的硬币。如果这笔钱不能由任何硬币组合成,则返回-1。

思路

动态规划:

  • 假设amount为10,硬币面额为[1,2,5,10],用dp[i]来表示金额i所需要的最少硬币数,那么显然dp[0]=0,因为金额0不需要任何硬币。
  • 此时如果我们取了个硬币5,显然dp[10]=dp[10-5]+1=dp[5]+1,那么此时dp[5]+1是最小值吗?不一定,因为如果取一枚金额为10的硬币就足够了,此时dp[10]=dp[10-10]+1=0+1=1.所以我们需要在取me某一枚硬币之后,需要更新当前dp[i]的值。 dp[i]=min(dp[i],dp[i-coin]+1)
  • 另外我们需要初始化dp,假设每一个硬币的面额都大于amount,此时我们是找不出硬币组合的,那么dp[amount]=-1,显然我们不能初始化所有值为-1(负数小于任何正数),我们应该初始化一个“最大值”,比如inf或者amount+1,当遍历所有金额之后,最后dp[amount]仍然为'最大值',说明这笔钱不能由任何硬币组合成,那么我们返回-1。取amount+1是因为:假设所有硬币金额都为1,那么dp[amount]的最大值都为amount,都会小于amount+1

代码实现

代码语言:javascript
复制
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[amount+1]*(amount+1)
        dp[0]=0
        for i in range(1,amount+1):
            for c in coins:
                if i>=c:
                    dp[i]=min(dp[i],dp[i-c]+1)
        if dp[amount]==amount+1:
            return -1
        return dp[amount]

参考资料

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.03.07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 思路
  • 代码实现
  • 参考资料
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档