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

wanting-for

zltzlt 发表于 2020-1-25 22:11
输入 amount = 500，coins = [1, 2, 5] 就会超时

算法不好，有待更改，迷上了递归，看见啥都想递归一下
这个用例大约用时15秒

zltzlt

wanting-for 发表于 2020-1-25 22:21
算法不好，有待更改，迷上了递归，看见啥都想递归一下
这个用例大约用时15秒

小心超出递归深度

wanting-for

zltzlt 发表于 2020-1-25 22:22
小心超出递归深度

嘿嘿，我想到优化方法了

776667

1. from itertools import product
   
2. 
   
3. def fun314(amount,coins):
   
4.     if amount%min(coins):
   
5.         repeat = (amount//min(coins))+1
   
6.     else:
   
7.         repeat = amount//min(coins)
   
8.     result = []
   
9.     for i in range(1,repeat+1):
   
10.         for j in product(coins,repeat=i):
    
11.             if sum(j)==amount and sorted(j) not in result:
    
12.                 result.append(sorted(j))
    
13.     return len(result)

复制代码

fan1993423

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

你这道题的想法是什么？

Croper

fan1993423 发表于 2020-1-31 23:12
你这道题的想法是什么？

还是动态规划。
在把硬币面值数组coins从小到大排序后，
使用l[a][ b]储存在要求金额为a时，使用前b+1种硬币能凑出的方案数量。
显然在a=0时，不管b为多少，结果都为0(不取任何硬币)。
在a!=0时，考虑凑出的方案中面值最大硬币其面值为coins[c]，那么剩余的硬币金额都不大于coins[c],可用方案数量为l[a-coins[c]][c]。且有c不大于 b。
即状态转移公式为l[a][ b]=l[a-coins[0]][0]+l[a-coins[1]][1]+...+l[a-coins[ b]][ b]
最终答案就为l[amount][len(coins)-1]

fan1993423

1. def fun314(amount,coins):
   
2.     coins.sort()
   
3.     dp=[[1]+[0]*amount for _ in range(len(coins)+1)]
   
4.     for i in range(1,len(coins)+1):
   
5.         for j in range(1,amount+1):
   
6.             if j>=coins[i-1]:
   
7.                 dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]
   
8.             else:
   
9.                 dp[i][j]=dp[i-1][j]
   
10.     return dp[-1][-1]

复制代码

kinkon

fan1993423 发表于 2020-4-17 02:04

虽然费空间，但是清晰易懂，赞

fan1993423

kinkon 发表于 2020-4-17 21:53
虽然费空间，但是清晰易懂，赞

zltzlt

fan1993423 发表于 2020-4-17 02:04

输入 amount = 11, coins = [1, 2, 5] 结果有误

fan1993423

zltzlt 发表于 2020-4-18 13:28
输入 amount = 11, coins = [1, 2, 5] 结果有误

难道输出的结果不是11吗？

zltzlt

fan1993423 发表于 2020-4-18 15:05
难道输出的结果不是11吗？

是 3

fan1993423

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，[1,2,5]）也是输出的11

zltzlt

fan1993423 发表于 2020-4-18 20:56
难道我的理解有误
11=11*1+0*2+0*5
=9*1+1*2+0*5

额……测试用例出错了

fan1993423

zltzlt 发表于 2020-4-19 13:21
额……测试用例出错了

耗时怎么样