小明去超市买东西,收款员需要找给他n元的零钱,现在收款员手上有三种零钱,1元、5元和10元,问收款员有多少种找零的方法?
时间: 2024-03-24 18:40:43 浏览: 160
货币找零计算找给顾客固定钱数的最小货币量
这是一个典型的动态规划问题,我们可以使用动态规划来解决。
设 $dp(i,j)$ 表示使用前 $i$ 种面额的零钱,找 $j$ 元钱的方案数,其中 $i$ 取值范围为 $[1,3]$,$j$ 取值范围为 $[0,n]$。
则状态转移方程为:
$$
dp(i,j) = \begin{cases}
1 & \text{if } j = 0 \\
0 & \text{if } i = 0 \text{ and } j > 0 \\
dp(i-1,j) & \text{if } j < w_i \\
dp(i-1,j) + dp(i,j-w_i) & \text{if } j \ge w_i
\end{cases}
$$
其中,$w_i$ 表示第 $i$ 种面额的零钱的面值。
最终的答案即为 $dp(3,n)$。
以下是 C++ 代码实现:
```cpp
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int n;
int dp[4][N];
int main() {
cin >> n;
for (int i = 0; i <= n; i++) {
dp[0][i] = 0;
dp[1][i] = dp[2][i] = 1;
}
for (int i = 1; i <= 3; i++) {
dp[i][0] = 1;
}
int w[4] = {0, 1, 5, 10};
for (int i = 2; i <= 3; i++) {
for (int j = 1; j <= n; j++) {
if (j < w[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-w[i]];
}
}
}
cout << dp[3][n] << endl;
return 0;
}
```
时间复杂度为 $O(n)$,空间复杂度为 $O(n)$。
阅读全文