美文网首页LeetCode
322. 零钱兑换

322. 零钱兑换

作者: cptn3m0 | 来源:发表于2019-03-12 21:44 被阅读0次
    class Solution(object):
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            # INF 表示无效
            INF = 0x3f3f3f
            dp = [INF]*(amount+1)
            
            # 初始化
            # 为啥初始化 dp[0] = 0
            # 表示使用coins组成0元的方法有几种? 
            dp[0] = 0
    
            for i in range(1, amount+1):
              
                for c in coins:
                    # 如果使用coin 来组合数据
                    if i>=c:
                      dp[i] = min(dp[i-c]+1,dp[i])
    
    
            if dp[amount] == 0x3f3f3f:
              return -1
            return dp[amount]
    

    相关文章

      网友评论

        本文标题:322. 零钱兑换

        本文链接:https://www.haomeiwen.com/subject/xtvopqtx.html