输入 amount = 500，coins = 就会超时
算法不好，有待更改，迷上了递归，看见啥都想递归一下{:5_109:}
这个用例大约用时15秒 wanting-for 发表于 2020-1-25 22:21
算法不好，有待更改，迷上了递归，看见啥都想递归一下
这个用例大约用时15秒
小心超出递归深度{:10_256:} zltzlt 发表于 2020-1-25 22:22
小心超出递归深度
嘿嘿，我想到优化方法了{:5_95:} from itertools import product
def fun314(amount,coins):
if amount%min(coins):
repeat = (amount//min(coins))+1
else:
repeat = amount//min(coins)
result = []
for i in range(1,repeat+1):
for j in product(coins,repeat=i):
if sum(j)==amount and sorted(j) not in result:
result.append(sorted(j))
return len(result) Croper 发表于 2020-1-25 15:18
总感觉还能优化
你这道题的想法是什么？
本帖最后由 Croper 于 2020-2-1 16:07 编辑
fan1993423 发表于 2020-1-31 23:12
你这道题的想法是什么？
还是动态规划。
在把硬币面值数组coins从小到大排序后，
使用l[ b]储存在要求金额为a时，使用前b+1种硬币能凑出的方案数量。
显然在a=0时，不管b为多少，结果都为0(不取任何硬币)。
在a!=0时，考虑凑出的方案中面值最大硬币其面值为coins，那么剩余的硬币金额都不大于coins,可用方案数量为l]。且有c不大于 b。
即状态转移公式为l[ b]=l]+l]+...+l][ b]
最终答案就为l def fun314(amount,coins):
coins.sort()
dp=[+*amount for _ in range(len(coins)+1)]
for i in range(1,len(coins)+1):
for j in range(1,amount+1):
if j>=coins:
dp=dp+dp]
else:
dp=dp
return dp[-1][-1] fan1993423 发表于 2020-4-17 02:04
虽然费空间，但是清晰易懂，赞 kinkon 发表于 2020-4-17 21:53
虽然费空间，但是清晰易懂，赞
{:5_110:} fan1993423 发表于 2020-4-17 02:04
输入 amount = 11, coins = 结果有误 zltzlt 发表于 2020-4-18 13:28
输入 amount = 11, coins = 结果有误
难道输出的结果不是11吗？ fan1993423 发表于 2020-4-18 15:05
难道输出的结果不是11吗？
是 3 zltzlt 发表于 2020-4-18 17:01
是 3
难道我的理解有误
11=11*1+0*2+0*5
=9*1+1*2+0*5
=7*1+2*2+0*5
=5*1+3*2+0*5
=3*1+4*2+0*5
=1*1+5*2+0*5
=6*1+0*2+1*5
=4*1+1*2+1*5
=2*1+2*2+1*5
=0*1+3*2+1*5
=1*1+0*2+2*5
共计11种方案，而且你选的最佳答案在输入(11，）也是输出的11 fan1993423 发表于 2020-4-18 20:56
难道我的理解有误
11=11*1+0*2+0*5
=9*1+1*2+0*5
额……测试用例出错了 zltzlt 发表于 2020-4-19 13:21
额……测试用例出错了
耗时怎么样{:10_256:}
页:
1
[2]