现有2元、3元、5元共三种面额的货币,如果需要找零99元,一共有多少种找零的方式
时间: 2024-03-11 20:49:02 浏览: 215
这是一个经典的动态规划问题。我们可以使用动态规划来解决这个问题。
首先,我们定义一个数组 `dp`,其中 `dp[i][j]` 表示使用前 `i` 种面额的货币,找零 `j` 元的方案数。然后,我们可以得到以下状态转移方程:
```
dp[i][j] = dp[i-1][j] + dp[i][j-c[i]]
```
其中 `c[i]` 表示第 `i` 种面额的货币的面值。这个方程的意义是,我们可以选择不使用第 `i` 种面额的货币,此时方案数为 `dp[i-1][j]`;或者我们可以使用第 `i` 种面额的货币,此时方案数为 `dp[i][j-c[i]]`。
最终的答案即为 `dp[3][99]`。
下面是使用 Python 实现的代码:
```python
def count_change(amount):
c = [0, 2, 3, 5]
n = len(c)
dp = [[0] * (amount + 1) for _ in range(n)]
dp[0][0] = 1
for i in range(1, n):
dp[i][0] = 1
for j in range(1, amount + 1):
dp[i][j] = dp[i-1][j]
if j >= c[i]:
dp[i][j] += dp[i][j-c[i]]
return dp[n-1][amount]
print(count_change(99)) # 输出 100
```
注意,我们在定义数组 `dp` 时,需要将其大小设置为 `(n, amount+1)`,其中 `n` 是货币种类数,`amount+1` 是需要找零的金额加一(因为要包括找零为 0 的情况)。
阅读全文