【动态规划】钢条切割问题

问题描述参见《算法导论》第十五章 动态规划，下面给出程序代码：

#include<stdio.h>
int max(int a,int b);
int calc(int p[],int n);
int p[11]={0,1,5,8,9,10,17,17,20,24,30};//p[i]存储长度为i的钢条价值
int r[101]={0};//r[i]存储总长度为i，切割(或者不切割)所能达到的最大价值
int main()
{
    int n;
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
    {
        calc(p,i);
        printf("%d ",r[i]);
    }
    return 0;   
}
int max(int a,int b)
{
    return a>b?a:b;
}
int calc(int p[],int n)
{
    int value;
    if(r[n]>0)
        return r[n];//长度为n的钢条能达到的最大价值已经求出来了，直接返回
    else if(n==0)
        value = 0;
    else 
    {
        value = -1;
        int i=1;
        for(i=1;i<=n;i++)
            value = max(value,p[i]+calc(p,n-i));//
    }
    r[n] = value;
    return value;   
}