小明去超市买东西,收款员需要找给他n元的零钱,现在收款员手上有三种零钱,1元、5元和10元,问收款员有多少种找零的方法?
时间: 2024-03-24 22:40:51 浏览: 26
这道题可以用动态规划来解决。
假设 dp[i] 表示找 i 元零钱的方法数,那么:
- 当 i < 1 时,dp[i] = 0,因为没有零钱可找。
- 当 i = 1 时,只有一种方法,即找一张 1 元零钱,所以 dp[1] = 1。
- 当 i = 5 时,有两种方法:一种是找五张 1 元零钱,另一种是找一张 5 元零钱,所以 dp[5] = 2。
- 当 i = 10 时,有四种方法:一种是找十张 1 元零钱,另一种是找两张 5 元零钱,还有一种是找一张 10 元零钱,最后一种是找五张 1 元零钱加上一张 5 元零钱,所以 dp[10] = 4。
对于其他的 i,可以根据以下公式进行计算:
dp[i] = dp[i-1] + dp[i-5] + dp[i-10]
因为找 i 元零钱的方法数等于找 i-1 元零钱的方法数加上找 i-5 元零钱的方法数加上找 i-10 元零钱的方法数。
最终的答案就是 dp[n]。
以下是一个 C++ 实现的例子:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int countChange(int n) {
vector<int> dp(n+1, 0);
dp[0] = 1; // 找零 0 元的方法数为 1
for (int i = 1; i <= n; i++) {
if (i >= 1) dp[i] += dp[i-1];
if (i >= 5) dp[i] += dp[i-5];
if (i >= 10) dp[i] += dp[i-10];
}
return dp[n];
}
int main() {
int n;
cout << "请输入需要找的零钱金额:";
cin >> n;
cout << "一共有 " << countChange(n) << " 种找零方法。" << endl;
return 0;
}
```
该程序使用了一个 vector 来存储每个金额的找零方法数,使用 for 循环遍历每个金额,根据上述公式计算出当前金额的找零方法数,最后返回 dp[n] 即可。