论坛 › Python交流 › Python：每日一题 314

zltzlt 发表于 2020-1-24 21:21:15

Python：每日一题 314

今天的题目：

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

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

示例 1：

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

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

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

{:10_298:}欢迎大家一起答题！{:10_298:}

Croper 发表于 2020-1-24 21:56:36

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

塔利班 发表于 2020-1-25 10:25:46

本帖最后由 塔利班 于 2020-1-25 10:32 编辑

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 11:00:20

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

输入 amount = 500，coins = 超时，加上 sort 也一样。

小甲鱼de粉丝 发表于 2020-1-25 11:09:51

春节快乐！先不解题

zltzlt 发表于 2020-1-25 11:11:07

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

新年快乐！

既然来了就想想呗{:10_264:}

阴阳神万物主 发表于 2020-1-25 13:01:54

为什么这题我有印象？

Croper 发表于 2020-1-25 15:18:33

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

zltzlt 发表于 2020-1-25 15:24:28

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

解答错误

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

Croper 发表于 2020-1-25 15:27:07

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=[*len(coins)]
    for i in range(1,amount+1):
      a,t=0,[]
      for j in range(len(coins)):
            if coins>i:
                t.extend(*(len(coins)-j))
                break
            a+=l]
            t.append(a)
      l.append(t)
    return l[-1][-1]

zltzlt 发表于 2020-1-25 15:32:51

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

解答错误

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

Croper 发表于 2020-1-25 15:38:28

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

输入：amount = 100, coins =


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

zltzlt 发表于 2020-1-25 15:39:15

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

336 ms

TJBEST 发表于 2020-1-25 18:00:43

输入：amount = 0, coins =
输出结果是什么呢？是1还是0

zltzlt 发表于 2020-1-25 18:10:56

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

1

TJBEST 发表于 2020-1-25 18:37:20

新年快乐！这个程序是初步的，我试了一下准确但是超时，我再想想办法改改，思路上得变化
def fun314(amount,coins):
    def inner(amount,position):
      temp = MaxToMin
      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=res + 1
                else:
                  inner(amount-div*temp,position + 1)
            elif amount == temp:
                res = res + 1
                inner(amount,position + 1)
            else:
                inner(amount,position + 1)
      else:
            if amount % temp == 0:
                res=res + 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 =
    inner(amount,0)
    return res

zltzlt 发表于 2020-1-25 19:04:11

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

输入 amount = 500，coins = 超时。

小甲鱼de粉丝 发表于 2020-1-25 20:25:55

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

既然来了就想想呗

好

wanting-for 发表于 2020-1-25 22:09:03

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)
      if sum(list_sum) == all:
            count+=1
      elif sum(list_sum)<all:
            list3 = list1
            #list_sum.append(i)
            count+=solve(list3,all,list_sum)
      m = list_sum.pop()
    return count
print(solve(,6))
输入这个amount = 500，coins = ，指定超时，而且调用堆栈也太多次，内存也会超。
不知道对于小数据是否准确

zltzlt 发表于 2020-1-25 22:11:36

wanting-for 发表于 2020-1-25 22:09
输入这个amount = 500，coins = ，指定超时，而且调用堆栈也太多次，内存也会超 ...

输入 amount = 500，coins = 就会超时

查看完整版本: Python：每日一题 314