C++数据结构--自顶向下和自底向上的动态编程思想

深碍√TFBOYSˉ_ 2021-11-05 00:34 346阅读 0赞

**1.自顶向下的动态编程  
Example:计算组合数  
组合定义：  
从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；  
从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m) 表示.  
  
  
推导：  
从M个元素中任意指定一个元素。则选出N个的方法中，包含这一个元素的有C（M-1，N-1）种组合，不包含这一个元素的有C（M-1，N）种组合  
  
递归公式：  
![20130810160113656][]  
  
  
使用自顶向下的动态编程实现计算组合数  
如果不使用动态编程，计算C（50,6）=15890700需执行3,813,767次函数递归调用，但使用动态编程只需执行441次函数调用  
实现代码：  
\#include<iostream>  
\#include<vector>  
using namespace std;  
  
  
//res向量数组保存递归返回结果  
//要求res至少有(n+1)(k+1)个元素，并初始化为-1   
int comb(int n,int k,vector<vector<int>> &res)  
\{   
int combVal;  
if(res\[n\]\[k\]!=-1)  
 return res\[n\]\[k\];  
if(k==0||k==n)  
 combVal= 1;  
else if(k==n)  
 combVal=n;  
else  
 combVal=comb(n-1,k,res)+comb(n-1,k-1,res);  
  
res\[n\]\[k\]=combVal;  
return combVal;  
\}  
  
  
测试代码  
  
 int main ()   
\{   
 int n;int k;  
 cout<<"input C(n,k)'s arguments n,k"<<endl;  
 cin>>n>>k;  
 vector<int> inner(k+1,-1);  
 vector<vector<int>> res(n+1,inner);   
 cout<<"result is: "<<comb(n,k,res)<<endl;  
  
 return 0;  
\}  
  
  
  
运行结果：  
![Center][]  
  
  
2.自底向上动态编程  
Example：同样是计算组合数  
自底向上计算C（n,k)组合数的所有结果刚好形成帕斯卡三角  
如n==6时：  
![20130810160419250][]  
  
  
  
实现代码：  
 int comb(int n,int k)  
\{  
vector<vector<int>> res; //存储所有以前计算的值，形成帕斯卡三角  
for(int i=0;i<n+1;i++)  
 res.push\_back(vector<int>(i+1,0));  //分配空间并初始为0  
  
 res\[0\]\[0\]=1; //设置0行  
 for(int i=1;i<=n;i++)  
 \{   
 res\[i\]\[0\]=1; //将第i行的第一项设为1  
 res\[i\]\[i\]=1; //将第i行的最后一项设为1  
  
 for(int j=1;j<i;j++) //使用i-1行的元素，使第i行各中间项为前一行的两项之和  
 res\[i\]\[j\]=res\[i-1\]\[j-1\]+res\[i-1\]\[j\];  
 \}  
 return res\[n\]\[k\];  
  
  
 \}**

[20130810160113656]: /images/20211104/1b2cbd53110f4ffc8b5f2b0b99f00534.png
[Center]: /images/20211104/407b6b0f293140ddb3cc46188e406fde.png
[20130810160419250]: /images/20211104/3019190db4cb4f02bf348b6f3506c27e.png