用50分、10分、5分、2分、1分的硬币来凑成1元,共有多少方法
时间: 2023-10-20 15:14:15 浏览: 79
我们可以使用动态规划来解决这个问题。
设 $dp[i][j]$ 表示使用前 $i$ 种硬币凑成 $j$ 分钱的方案数,其中硬币的面值为 $coins_i$。
则对于第 $i$ 种硬币,有两种情况:
1. 不使用第 $i$ 种硬币,则方案数为 $dp[i-1][j]$;
2. 使用第 $i$ 种硬币,则方案数为 $dp[i][j-coins_i]$。
因此,状态转移方程为:
$$
dp[i][j] = dp[i-1][j] + dp[i][j-coins_i]
$$
边界条件为 $dp[i][0] = 1$,即不需要硬币就可以凑成 $0$ 分钱的方案数为 $1$。
最终答案为 $dp[5][100]$,即使用前 $5$ 种硬币凑成 $100$ 分钱的方案数。
以下是Python代码实现:
```python
coins = [1, 2, 5, 10, 50] # 硬币面值
n = len(coins)
target = 100 # 目标金额
dp = [[0] * (target+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = 1
for i in range(1, n+1):
for j in range(1, target+1):
dp[i][j] = dp[i-1][j]
if j >= coins[i-1]:
dp[i][j] += dp[i][j-coins[i-1]]
print(dp[n][target])
```
输出结果为:
```
293
```
因此,用50分、10分、5分、2分、1分的硬币来凑成1元,共有293种方法。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)