前面的算法是朴素递归算法，之所以会计算那么久是因为不断的调用递归过程，且没有保存子问题的值，下面介绍两种改进的方法

1：带备忘的自顶向下法，此方法仍然按自然的递归形式编写过程，但过程会保存每个子问题的解，而当需要一个子问题的解时，过程会首先检查是否已经保存过此解，如果是，则直接返回保存的值，从而节省计算时间，否则，按通常方式计算这个子问题，之所以称这个过程为带备忘的，是因为它记住了之前已经计算出的结果，下面贴出我自己写的代码。

#include
     
      #include
      
       using namespace std;int p[1000], r[1000];int MEMOIZED_CUT_ROD_AUX(int* p, int n, int* r){    int q;    if(r[n] >= 0)        return r[n];    if(n == 0)    {        q = 0;    }    else    {        q = -1e8;    }    for(int i = 1; i <= n; i++)    {        q = max(q,p[i]+MEMOIZED_CUT_ROD_AUX(p, n-i, r));    }    r[n] = q;    return q;}int MEMOIZED_CUT_ROD(int* p, int n){    for(int i = 0; i <=n; i++)    {        r[i] = -1e8;    }    return MEMOIZED_CUT_ROD_AUX(p, n, r);}int main(){    int n = 0, q = 0;    clock_t start, finish;    double duration = 0.0;    p[0] = 0;    p[1] = 1;    p[2] = 5;    p[3] = 8;    p[4] = 9;    p[5] = 10;    p[6] = 17;    p[7] = 17;    p[8] = 20;    p[9] = 24;    p[10] =30;    cout << "请输入钢管长度：";    cin >> n;    start = clock();    q = MEMOIZED_CUT_ROD(p, n);    cout << "收益为：" << q <
      
     

 

 

运行时间减少了很多，效果明显，结果不变