要求按5分、2分和1分硬币的数量依次从大到小的顺序,输出各种换法。每行输出一种换法,格式为:“fen5:5分硬币数量, fen2:2分硬币数量, fen1:1分硬币数量, total:硬币总数量”。最后一行输出“count = 换法个数”。
时间: 2024-05-13 19:15:30 浏览: 28
好的,这是一个简单的动态规划问题,我们可以使用迭代的方式计算出所有的换法,然后输出即可。下面是代码实现:
```python
def coin_change(n):
"""
:param n: int
:return: None
"""
dp = [0] * (n+1)
dp[0] = 1
for coin in [5, 2, 1]:
for i in range(coin, n+1):
dp[i] += dp[i-coin]
count = dp[n]
print(f"count = {count}")
for i in range(count):
print(f"fen5:{dp[n-i*5*count]//5}, fen2:{dp[n-i*5*count]%5//2}, fen1:{dp[n-i*5*count]%5%2}, total:{n}")
```
可以看出,我们首先初始化一个长度为 n+1 的数组 `dp`,其中 `dp[i]` 表示凑出 i 分钱的换法数量。然后我们依次考虑 5 分、2 分和 1 分硬币,对于每种硬币,我们从面额开始遍历,计算出新的换法数量,最后输出即可。