算法导论-动态规划

钢筋分割问题
长度i对应价格p(i)
那么给定长度i，如何分割才能够使得收益最大呢？
动态规划是将问题划分子问题然后求解，所以动态规划的前提是问题是可分解成子问题的。

由于每一节都有两种情况分，或者部分，所以总共有2^(n-1)次方的分解方法。
解法一：
  
 cutFc(int n,p)
{
   int q;
   if n == 0
        return 0;
    else 
     q=0;
      for(i=1;i<=n;i++)
          q = max(q,p[i]+cutFc(n-i,p));
    return q;
}
解法二：
   带备忘录的算法解决方案,只是加了一个变量的存储功能就让整个效率高了起来：
 cutFc(int n,p，int *r)
{
   int q;
    if(r[n]>=0)
         return r[n];
     if n == 0
        return 0;
    else 
     q=0;
      for(i=1;i<=n;i++)
          q = max(q,p[i]+cutFc(n-i,p));
    r[n] = q;
    return q;
}