动态规划与分治法：

            相同点：都是通过组合子问题的解来求解原问题；

        不同点：分治法的子问题是互不相交的子问题，而动态规划则应用于子问题的重叠相比分治法少多了许多不必要的运算；

动态规划方法常用来解决最优问题，动态规划算法步骤如下：

            A：刻画一个最优解的结构特征；

            B：递归的定义最优解的值；

            C：计算最优解的值，通常采用自底向上的方法；

            D：利用计算出的信息构造一个最优解。

钢条切割问题：

长度 i:       1           2          3          4            5             6            7        8          9            10

 价格pi      1           5          8          9           10           17         17       20         24           30

       程序源代码如下（c语言有详细的注释方便阅读）：

http://s1/mw690/002cacfOgy6Ma9KI14kf0&690

http://s2/mw690/002cacfOgy6Ma9LjZF7a1&690

#include< stdio.h>
int arr[11]={0,1,5,8,9,10,17,17,20,24,30};  //为什么在价格数组添加一项0，是为了让数组arr[1]=1;这一点为后面解题带来很大的方便；
void personal(int b);
//static int q;
int k=0,w;
//  比较两个数的大小，返回最大值； 
int MAX(int m,int n)
{
return m>n?m:n;
}
//普通的自底向上递归； 
int CUT_ROD(int *p,int n)
{
if(n==0)
{
return 0;
}
int q=-1;
for(int i=1;i<= n;i++)
{
q=MAX(q,p[i]+CUT_ROD(p,n-i));    //该分割的切割方案有2^(n-1)种；如果钢条长度是b切割是从 1，b-1个1，依次下去；
                //每一次将钢条切成两部分从最小的b个1开始依次到0，和b；从中分配方案比较多的；2^(b-1)种;
                       //缺点：由计算方案从而确定了效率很低，并且只知道最优收益的值，确未能保存钢条的切割分配方案； 
}
return q;
}
//带备忘的自顶向下法 
int MEMOIZED_CUT_ROD_AUX(int *p,int n,int *r)
{
int q=-1;
if(r[n]>=0)
{
return r[n];     //如果他的值比0大，则，说明保存了r[n]的值，从而直接返回它的值； 
}
if(n==0)
      q=0;
else 
     {
        
for(int i=1;i<= n;i++)
{
q=MAX(q,p[i]+MEMOIZED_CUT_ROD_AUX(p,n-i,r));
    //printf("#%d,",p[i]);         //我会经常用到这些语句去查看运行数据的过程，是否是按照预想的进行着；目的方便调试；
                               //（例如i的值忘记等于n这样的错误） 
}

r[n]=q;                       //将q的值保存到数组r[n]中； 
   }
     
return q;
}
//辅助函数初始化；
int MEMOIZED_CUT_ROD(int *p,int n)
{
int r[11];
for(int i=0;i<= n;i++)
{
r[i]=-1;                  //对数组初始化，只需初始值小于0的任意整数； 
}
return MEMOIZED_CUT_ROD_AUX(p,n,r);
 
} 
//自底向上的递归； 
int BUTTOM_CUT_ROD(int *p,int n) 
{
int r[11];
r[0]=0;
int q; 
for(int j=1;j<= n;j++)
{
q=-1;
for(int i=1;i<= j;i++)
{
q=MAX(q,p[i]+r[j-i]);         //很显然没有调用递归，而是双重循环；时间复杂度为O(n*n)； 
//printf("#%d,",j);                //目的做调试程序用； 
}
r[j]=q;
}
return q;
}
        //重构解的目的是去知道分割方案，并打印最优解收益值相对应的分割方案； 
int EXTENDED_BOTTOM_UP_CUT_ROD(int *p,int n)
{
int r[11],s[11];
r[0]=0;
int q;
for(int j=1;j<= n;j++)
{
q=-1;
for(int i=1;i<= j;i++)
{
if(q

q=p[i]+r[j-i];
s[j]=i;

// printf("#%d,%d\n",s[j],n-s[j]);


}
r[j]=q;
}
for(int j=1;j<= n/2;j++)
{
printf("切割分法#%d,%d,收益%d\n",s[j],n-s[j],p[j]+p[n-j]);
if(k

{
k=p[j]+p[n-j];
w=j;      //和我单独编写的程序一样，将最优值的钢条分割长度保留； 
}
   }
   return q;
}


int main()
{


int b;
printf("请输入需要切割的钢条长度（<=10）\n");   //由于受价格数组的限制，从而只能输入小于等于10的钢条长度；
//如果想扩大，就先扩大价格数组就可以啦！ 
while(scanf("%d",&b)!=EOF)  //这样的输入是方便不停地测试数据，知道按CTRL+Z才结束程序运行； 
{

personal(b);
printf("普通的自顶向下的最优收益：%d\n",CUT_ROD(arr,b));
printf("带备忘的自顶向下的最优收益：%d\n",MEMOIZED_CUT_ROD(arr, b));
printf("普通的自底向上的最优收益：%d\n",BUTTOM_CUT_ROD(arr, b));
printf("重构的自底向上%d切割成 -和 -:最优收益：%d\n",b,w,b-w,EXTENDED_BOTTOM_UP_CUT_ROD(arr, b));
    }
return 0;
} 
     //这个程序是了解钢条切割后独立编写的程序； 
void personal(int b)
{     
  int i,j,max=0,c;
        int sum[b/2];              //定义一个用来存取收益的数组，由于切割的次数是对称的，则只需要一半； 
for(i=0;i<=b;i++)
{

for(j=b-i;j>0;j--)
{
if(b==i+j&&i<=b/2)            //钢条的分割长度不变，为b常数； 
{

sum[i]=arr[i]+arr[j];        //将每次的切割方案的收益保存到数组sum中； 
printf("%d切割成 -和 -:收益为 =\n",b,i,j,sum[i]);//打印是为了能够更加清晰地知道切割的数目与结果； 
   }
}
}
      for(i=0;i<=b/2;i++)
    {
    if(sum[i]>max)
       {
         max=sum[i];    // 最优值的存取； 
        // printf("%d,",max);
         c=i;             //最优值钢条的分割的 长度； 
     }
    
         
     }
     printf("最优：%d切割成 -和 -:收益为 %d\n",b,c,b-c,max);
}

总结：动态规划钢条切割运用的递归解决问题，或者说是分解问题为子问题；这也让我们对递归有了更加深刻的理解与认识；相比我的开始单独编写的程序，我编写的程序是只能解决只能将钢条分成两部分的解决方法；而书本中的是将钢条分割成n个都能够实现；我从中也能够很清晰的了解到递归解决实际问题的强大；递归典型的将问题分解为子问题，代码简单清晰明了，只是需要改进的是它的时间复杂度就相对比较大；希望能够通过后面的学习想到一些方法去优化它；如有改进和错误希望帮忙留言指出！