写一段符合上述要求的C++程序代码
时间: 2024-12-16 18:32:14 浏览: 1
cpp代码-02 邹红量 C++程序测试
在C++中,我们可以使用动态规划来解决这个问题,因为递归可能会导致大量的重复计算。这里是一个使用迭代而不是递归的例子,它使用了`std::vector`来存储中间结果并消除重复:
```cpp
#include <vector>
using namespace std;
int calculateCombinations(int n, int r) {
vector<vector<int>> dp(r+1, vector<int>(n+1)); // 初始化动态规划表
dp[0][0] = 1; // 基础情况,取0个数时有1种组合
for (int i = 1; i <= n; ++i) { // 遍历1到n
for (int j = 1; j <= min(i, r); ++j) { // 取1到当前数i的组合
dp[j][i] = dp[j-1][i-1]; // 根据组合公式计算
if (j > 1) // 考虑包含第j个元素的情况
dp[j][i] += dp[j][i-1];
}
}
return dp[r][n]; // 返回最终结果,即n个数中取r个数的组合数
}
阅读全文