[已解决]Python：每日一题 314

zltzlt

今天的题目：

给定若干不同面额的硬币（coins）和总金额（amount），计算可以凑成总金额的硬币组合数。

说明：每一种面额的硬币均有无限个。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3。

示例 3：

输入：amount = 10, coins = [10]
输出：1

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-25 15:38:28

zltzlt 发表于 2020-1-25 15:32
解答错误

输入：amount = 100, coins = [99, 1]

我去，sort弄掉了

def func314(amount:int,coins:list)->int:
    if len(coins)==0:
        if amount==0:
            return 1
        else:
            return 0
    coins.sort()        
    l=[[1]*len(coins)]
    for i in range(1,amount+1):
        a,t=0,[]
        for j in range(len(coins)):
            if coins[j]>i:
                t.extend([a]*(len(coins)-j))
                break
            a+=l[i-coins[j]][j]
            t.append(a) 
        l.append(t)
    return l[-1][-1]

跳转到最佳答案楼层

Croper

春节快乐，呃，明天再想。

塔利班

def f314(amount,coins):
    res=0
    c=len(coins)
    #coins.sort()  好像没用，如果性能不行加上试试看
    def dp(a,c):
        nonlocal res
        if not a:
            res+=1
        elif not c:
            return
        else:
            b=c[-1]
            for i in range(0,a+1,b):
                dp(a-i,c[:-1])
    dp(amount,coins)
    return res

先写个

zltzlt

塔利班 发表于 2020-1-25 10:25
先写个

输入 amount = 500，coins = [3, 5, 7, 8, 9, 10, 11] 超时，加上 sort 也一样。

小甲鱼de粉丝

春节快乐！先不解题

zltzlt

小甲鱼de粉丝 发表于 2020-1-25 11:09
春节快乐！先不解题

新年快乐！

既然来了就想想呗

阴阳神万物主

为什么这题我有印象？

Croper

总感觉还能优化

def func314(amount:int,coins:list)->int:
    if len(coins)==0:
        return 0
    coins.sort()
    l=[[1]*len(coins)]
    for i in range(1,amount+1):
        a,t=0,[]
        for j in range(len(coins)):
            if coins[j]>i:
                t.extend([a]*(len(coins)-j))
                break
            a+=l[i-coins[j]][j]
            t.append(a) 
        l.append(t)
    return l[-1][-1]

zltzlt

Croper 发表于 2020-1-25 15:18
总感觉还能优化

解答错误

输入：amount = 0, coins = []
输出：0
预期结果：1

Croper

zltzlt 发表于 2020-1-25 15:24
解答错误

输入：amount = 0, coins = []

这用例够刁钻~

def func314(amount:int,coins:list)->int:
    if len(coins)==0:
        if amount==0:
            return 1
        else:
            return 0
    l=[[1]*len(coins)]
    for i in range(1,amount+1):
        a,t=0,[]
        for j in range(len(coins)):
            if coins[j]>i:
                t.extend([a]*(len(coins)-j))
                break
            a+=l[i-coins[j]][j]
            t.append(a) 
        l.append(t)
    return l[-1][-1]

zltzlt

Croper 发表于 2020-1-25 15:27
这用例够刁钻~

解答错误

输入：amount = 100, coins = [99, 1]
输出：1
预期结果：2

Croper

zltzlt 发表于 2020-1-25 15:32
解答错误

输入：amount = 100, coins = [99, 1]

我去，sort弄掉了

def func314(amount:int,coins:list)->int:
    if len(coins)==0:
        if amount==0:
            return 1
        else:
            return 0
    coins.sort()        
    l=[[1]*len(coins)]
    for i in range(1,amount+1):
        a,t=0,[]
        for j in range(len(coins)):
            if coins[j]>i:
                t.extend([a]*(len(coins)-j))
                break
            a+=l[i-coins[j]][j]
            t.append(a) 
        l.append(t)
    return l[-1][-1]

zltzlt

Croper 发表于 2020-1-25 15:38
我去，sort弄掉了

336 ms

TJBEST

输入：amount = 0, coins = [1,2,3,4]
输出结果是什么呢？是1还是0

zltzlt

TJBEST 发表于 2020-1-25 18:00
输入：amount = 0, coins = [1,2,3,4]
输出结果是什么呢？是1还是0

1

TJBEST

新年快乐！这个程序是初步的，我试了一下准确但是超时，我再想想办法改改，思路上得变化

def fun314(amount,coins):
    def inner(amount,position):
        temp = MaxToMin[position]
        if position < M - 1:
            if amount > temp:
                div = amount // temp 
                for i in range(0,div):
                    inner(amount-i*temp,position + 1)
                if amount % temp == 0:
                    res[0]=res[0] + 1
                else:
                    inner(amount-div*temp,position + 1)
            elif amount == temp:
                res[0] = res[0] + 1
                inner(amount,position + 1)
            else:
                inner(amount,position + 1)
        else:
            if amount % temp == 0:
                res[0]=res[0] + 1
            else:
                pass
            
    if coins == []:
        if amount == 0:
            return 1
        else:
            return 0
    else:
        pass
  
    if amount == 0:
        return 1
    else:
        pass
 
    MaxToMin = sorted(coins)
    MaxToMin.reverse()
    M = len(MaxToMin)
    res = [0]
    inner(amount,0)
    return res[0]

zltzlt

TJBEST 发表于 2020-1-25 18:37
新年快乐！这个程序是初步的，我试了一下准确但是超时，我再想想办法改改，思路上得变化

输入 amount = 500，coins = [3, 5, 7, 8, 9, 10, 11] 超时。

小甲鱼de粉丝

zltzlt 发表于 2020-1-25 11:11
新年快乐！

既然来了就想想呗

好

wanting-for

def solve(list1:list,all,list_sum=[],list3=[]):
    list1.sort()
    list1.reverse()
    count = 0
    if all == 0:
        return 1
    for i in range(len(list1)):
        list_sum.append(list1[i])
        if sum(list_sum) == all:
            count+=1
        elif sum(list_sum)<all:
            list3 = list1[i:]
            #list_sum.append(i)
            count+=solve(list3,all,list_sum)
        m = list_sum.pop()
    return count
print(solve([3,2,1],6))  

输入这个amount = 500，coins = [3, 5, 7, 8, 9, 10, 11]，指定超时，而且调用堆栈也太多次，内存也会超。
不知道对于小数据是否准确

zltzlt

wanting-for 发表于 2020-1-25 22:09
输入这个amount = 500，coins = [3, 5, 7, 8, 9, 10, 11]，指定超时，而且调用堆栈也太多次，内存也会超 ...

输入 amount = 500，coins = [1, 2, 5] 就会超时