C++用1元、2元、5元组成10元,编程计算方法。.
时间: 2023-12-17 21:02:52 浏览: 90
这是一个典型的动态规划问题,可以采用自底向上的方式进行求解。具体的实现过程如下:
1. 定义一个一维数组dp,其中dp[i]表示组成i元需要的最少硬币数量。
2. 初始化dp[0]=0。
3. 对于每个i>=1,计算dp[i]的值。具体地,对于每一种硬币面值j,如果j<=i,那么dp[i]的值可以通过dp[i-j]+1来更新,其中dp[i-j]表示组成i-j元需要的最少硬币数量,而1则表示使用了面值为j的硬币。
4. 最终,dp[10]即为所求的答案。
以下是C++的实现代码:
```c++
#include <iostream>
#include <climits>
using namespace std;
int main() {
int dp[11];
dp[0] = 0;
for (int i=1; i<=10; i++) {
dp[i] = INT_MAX; // 初始化为无穷大
if (i>=1 && dp[i-1]!=INT_MAX) dp[i] = min(dp[i], dp[i-1]+1);
if (i>=2 && dp[i-2]!=INT_MAX) dp[i] = min(dp[i], dp[i-2]+1);
if (i>=5 && dp[i-5]!=INT_MAX) dp[i] = min(dp[i], dp[i-5]+1);
}
cout << dp[10] << endl;
return 0;
}
```
输出结果为2,表示组成10元需要的最少硬币数量为2。
阅读全文