C++数据结构--动态编程

- 日理万妓 2021-11-04 19:40 264阅读 0赞

**1.动态编程  
当分而治之算法划分的子问题不是相互独立时，直接的递归实现会因为子问题相互重叠导致惊人的多余计算和函数调用，甚至为指数递增  
Example:用递归实现斐波那契序列  
![20130810141651609][]  
  
实现代码：  
 int fib(int n)  
\{  
if(n<=1)  
 return n;  
else  
 return fib(n-1)+fib(n-2);  
\}  
  
  
![20130810141738140][]  
  
  
  
  
\*用自顶向下的动态编程可以去除多余的计算和函数调用，从而使函数的时间复杂度达到O（n).  
自顶向下策略在递归执行遇到停止条件得出中间结果时，将这些结果存储起来  
  
使用动态编程改进斐波那契数的计算  
(方框下的数字指明了执行的顺序；画了圈的节点的值已经在中间结果向量存储过,可以直接返回结果;阴影结点代表多余的计算）  
![20130810141916171][]  
Example:  
  
  
实现代码：  
\#include<iostream>  
\#include<vector>  
using namespace std;  
  
  
//res向量数组保存递归返回结果  
//要求res至少有n+1个元素，并初始化为-1   
int fib(int n,vector<int> &res)  
\{  
int fibVal;  
if(res\[n\]!=-1)  
 return res\[n\];  
if(n<=1)  
 fibVal= n;  
else  
 fibVal=fib(n-1,res)+fib(n-2,res);  
  
res\[n\]=fibVal;  
return fibVal;  
\}  
  
  
//填充向量数组，使其全为-1  
void fill(vector<int> &v)  
\{  
for(int i=0;i<v.size();i++)  
 v\[i\]=-1;  
\}  
  
  
测试代码：  
 int main ()  
\{  
vector<int> res;  
for(int i=0;i<10;i++)  
\{  
res.resize(i+1);  
fill(res);  
cout<<fib(i,res)<<ends;  
  
\}  
  
  
  
return 0;  
\}  
  
  
  
运行结果：  
![Center][]**

[20130810141651609]: /images/20211104/80c84cd617e14bbbb2f0aad6b92f369c.png
[20130810141738140]: /images/20211104/2cbb23db27ef4386b7782424d7e267d0.png
[20130810141916171]: /images/20211104/48e7d343de28495487a4f6c5952d137c.png
[Center]: /images/20211104/95a9a1c39539462aa7af7dd15171ca6d.png