我与动态规划-2

669.换硬币

题目

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

样例1

输入：
[1, 2, 5]

11

输出： 3

解释： 11 = 5 + 5 + 1

样例2

输入：

[2]

3

输出： -1

代码

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
        # F =np.array([])
        # for i in range(amount+1):
            # F=np.append(F,10000)
            # F[i]=10000
        # print(F)
        # F=zeros(amount+1)
        F=[10000 for i in range(amount+1)]
        # print(F)
        F[0]=0  #初始条件
        
        #转移方程
        # min(F[amount-coins[i]]+1)
        # amount-coins>=0
        for i in range(amount+1):
            # F[i]=10000
            for j in coins:
                if i-j>=0 and F[i-j]+1 < F[i] :
                    F[i]= F[i-j]+1
        # print(F)
        # for a,b in range(amount+1),F:
        for a,b in enumerate(F):
            if b == 10000:
                F[a]=-1
        print(F)        
        return F[amount]
ss= Solution()   
# coins=[1,2,5] 
# amount=11
result=ss.coinChange(coins,amount)
print(result)

总结

运行结果还不错，但是动态规划类题，还是那个经典两问：

• 1. 能否继续优化时间空间复杂度
• 2. 还有没有其他的算法解决

-------------本文结束感谢您的阅读-------------

赏

谢谢你请我喝咖啡

支付宝

微信