C++用1元、2元、5元组成10元,编程计算有几种方法。.
时间: 2023-09-10 16:07:45 浏览: 119
这是一个典型的动态规划问题,可以使用动态规划算法解决。
我们定义 `dp[i][j]` 表示使用前 i 种硬币组成 j 元钱的方案数。则有以下状态转移方程:
- 如果不使用第 i 种硬币,则 `dp[i][j] = dp[i-1][j]`
- 如果使用第 i 种硬币,则 `dp[i][j] = dp[i][j-coins[i]]`
- 综合上述两种情况,`dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]`
其中,`coins` 数组表示硬币的面额,本题中为 {1, 2, 5}。
最终答案为 `dp[3][10]`,即使用 1 元、2 元、5 元硬币组成 10 元的方案数。
下面是 C++ 的代码实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> coins{1, 2, 5};
vector<vector<int>> dp(4, vector<int>(11, 0));
dp[0][0] = 1;
for (int i = 1; i <= 3; i++) {
dp[i][0] = 1;
for (int j = 1; j <= 10; j++) {
dp[i][j] = dp[i-1][j];
if (j >= coins[i-1]) {
dp[i][j] += dp[i][j-coins[i-1]];
}
}
}
cout << dp[3][10] << endl;
return 0;
}
```
输出结果为 10,即共有 10 种组合方式。
阅读全文