669. 换硬币（dp动态规划）

669. 换硬币

中文English

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

样例

样例1

输入：
[1, 2, 5]
11
输出： 3
解释： 11 = 5 + 5 + 1

样例2

输入： 
[2]
3
输出： -1

注意事项

你可以假设每种硬币均有无数个
总金额不会超过10000
硬币的种类数不会超过500, 每种硬币的面额不会超过100

 

输入测试数据 (每行一个参数)如何理解测试数据？

 

返回所需最少硬币数量以及所需的硬币

import sys
##换硬币,如果需要返回 最小需要多少硬币数, 以及所需的硬币
class Solution:
    '''
    大致思路：[2,5,7] 27总数为例 时间复杂度O(len(coins)*amount)
    动态规划dp
    1.确定状态:最后一步，和子问题。大致意思就是开一个数组，数组的每个元素f[i]或者f[i][j]分别代表什么，类似于解数学题中的，X，Y，Z代表什么
    2.转移方程
    3.初始条件和边界情况
    4.计算顺序
    '''
    def coinChange(self, coins, amount):
        #初始条件,[无穷，无穷，无穷....],总共28位，从0到27,空间复杂度O(amount)
        res = [sys.maxsize]*(amount+1)
        d = [[]]*(amount+1)

        #如果总数为0，则只需要0个硬币
        res[0] = 0
        #从总数为1,2,3一直到27为止，也就是amount，循环amount次数
        for i in range(1,amount+1):
            
            #循环len(couins)次数
            for coin in coins:
                #因为res是从0,1,2..amount结束，并没有设置res[负数]的情况，所以需要跳过，res范围是从0到27结束，空间复杂度O(amount)
                if  i - coin < 0:
                    continue

                #res[i] = min(无穷，上一个硬币总数 + 当前1次),例如第7个
                '''
                如果coin为2，则min(无穷,res[7-2] + 1) >> res[7-2] = res[5] 此时硬币数为1，+ 当前coin=2，一次 >> 硬币数2
                如果coin为5，则min(无穷，res[7-5] + 1) >> res[7-5]=res[2] 此时硬币数为1， + 当前coin = 5，一次 >> 硬币数2
                如果coin为7，则min(无穷，res[7-7] + 1) >> res[7-7] =res[0] 此时硬币数为0， + 当前一个coin = 7,一次 >>硬币数1
                然后根据上面的硬币数得到最小，就是当前总数7，所需要的最小硬币数量了 >>>>>>>>>>>>>> 1
                '''
                #如果是硬币总数小于无穷或者上一个硬币总数的话，则更新
                if res[i] > res[i-coin]+1:
                    d[i] = d[i-coin] + [coin]

                res[i] = min(res[i],res[i-coin] + 1)


        if res[amount] == sys.maxsize:
            return -1
        print(d[amount])
        return res[amount]
result = Solution().coinChange([7, 2, 5],27)
print(result)

lintcode版本

class Solution:
    """
    @param coins: a list of integer
    @param amount: a total amount of money amount
    @return: the fewest number of coins that you need to make up
    """
    def coinChange(self, coins, amount):
        # write your code here
        
        #首先给定空间O(amount),从0,1,2...amount,空间复杂度O(amount)
        res = [sys.maxsize]*(amount+1)
        #如果总数为0，则硬币总数为0 
        res[0] = 0 
        
        #从总数1一直循环到amount,时间复杂度O(amount)*(len(coins))
        #每一步总数进行计算出最小值
        for i in range(1,amount+1):
            
            for coin in coins:
                #如果当前总数为1,1 -2 <0,则跳过，没有res[-1]的硬币总数，res硬币总数是从0开始的，0,1,2,3...amount,空间复杂度O(amount)
                if  i - coin < 0:
                    continue
                #min(无穷或者刚刚被替换的硬币总数，上一个硬币总数 + 当前硬币1个)
                res[i] = min(res[i],res[i-coin] + 1)
        
        if res[amount] == sys.maxsize:
            return -1 
        return res[amount]