c++如何用动态规划计算组合数
时间: 2024-05-29 12:04:50 浏览: 29
要使用动态规划计算组合数,我们可以使用一个二维数组C[m][n]来存储组合数的值。其中,C[i][j]表示从i个元素中选择j个元素的组合数。
我们可以使用以下递推关系式来计算C[i][j]:
- 当j=0或j=i时,C[i][j]=1;
- 否则,C[i][j]=C[i-1][j]+C[i-1][j-1]。
按照这个递推关系式,我们可以使用两个嵌套循环来填充数组C。首先,我们将数组C的第一列和对角线上的元素初始化为1。然后,我们使用上述递推关系式计算剩余的组合数。
接下来,让我们看一个示例代码来说明如何使用动态规划计算组合数:
```c++
#include <iostream>
using namespace std;
#define MaxSize 100
int C[MaxSize][MaxSize];
int combinat(int m, int n) {
for(int i=0; i<m; i++) {
for (int j=0; j<=i+1; j++) {
if (j == 0 || j == i+1)
C[i][j] = 1;
else
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
return C[m-1][n];
}
int main() {
for (int m = 1; m <= MaxSize; m++) {
C[m-1][m] = 1;
C[m-1][0] = 1;
}
cout << combinat(3, 2) << endl;
getchar();
}
```
这个示例代码使用动态规划的方法计算从3个元素中选择2个元素的组合数,并输出结果为3。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)