凑钱1元2元5元凑20元钱有多少种可能
时间: 2024-05-15 16:12:21 浏览: 15
这是一个典型的硬币组合问题,可以使用动态规划算法来解决。
设 $dp[i][j]$ 表示使用前 $i$ 种硬币凑齐 $j$ 元钱的方案数,则有状态转移方程:
$$dp[i][j] = dp[i-1][j] + dp[i][j-c_i]$$
其中,$c_i$ 表示第 $i$ 种硬币的面值。
初始化:$dp[0][0] = 1$,表示不使用任何硬币凑齐 0 元钱的方案数为 1。
最终的答案为 $dp[n][20]$,其中 $n$ 表示硬币的种类数。
Python 代码如下:
```python
coins = [1, 2, 5]
n = len(coins)
target = 20
dp = [[0] * (target+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(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])
```
输出结果为 40,即凑 20 元钱的方案数共有 40 种。
相关问题
python实现10元,5元,2元纸币凑整
可以使用贪心算法来实现。
首先将面值从大到小排序,然后从大面值开始尽量多的取,直到无法再取为止,然后依此类推。
具体实现代码如下:
```python
def money_change(num):
money_list = [10, 5, 2]
change_list = []
for money in money_list:
while num >= money:
num -= money
change_list.append(money)
return change_list if num == 0 else None
```
其中,`num` 表示需要凑整的金额,`money_list` 表示面值列表,`change_list` 用于存储结果。
测试一下:
```python
>>> money_change(23)
[10, 10, 2, 1]
>>> money_change(7)
[5, 2]
>>> money_change(20)
[10, 10]
>>> money_change(3)
None
```
可以看到,当金额无法凑整时,返回 `None`。
3枚硬币1个1分,一个2分,一个5分用多少种方法凑齐10元
这个问题可以回答。要凑齐10元,可以先将所有硬币的面值都转换成“分”,即1分、2分和5分,那么10元相当于1000分。现在问题就转化成了如何用1分、2分和5分的硬币凑出1000分的问题。我们可以使用动态规划的方法来解决这个问题。
定义一个二维数组dp[i][j]表示用前i个硬币凑出j分的方法数。对于第i个硬币,有两种情况:
1. 不使用第i个硬币,那么凑出j分的方法数就是用前i-1个硬币凑出j分的方法数,即dp[i-1][j]。
2. 使用第i个硬币,那么凑出j分的方法数就是用前i个硬币凑出j-coins[i]分的方法数,即dp[i][j-coins[i]]。
因此,状态转移方程为:dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]。
最终的答案就是dp[3][1000],即用3枚硬币凑出1000分的方法数。
代码实现如下:
```python
coins = [1, 2, 5]
dp = [[0] * 1001 for _ in range(4)]
dp[0][0] = 1
for i in range(1, 4):
for j in range(1001):
dp[i][j] = dp[i-1][j]
if j >= coins[i-1]:
dp[i][j] += dp[i][j-coins[i-1]]
print(dp[3][1000])
```
输出结果为:7275,即用3枚硬币凑出10元的方法数为7275种。