#include<iostream>
#include<time.h>
using namespace std;
#define inf -9999
int  memorized_cut_rod_aux(int p[],int n,int r[])
{
	int q=0;
	if(r[n]>=0)
	{
		return r[n];
	}
	else
	{
		//int q=inf;
		for(int i=1;i<=n;++i)
		{
			q=q>(p[i]+memorized_cut_rod_aux(p,n-i,r))?q:(p[i]+memorized_cut_rod_aux(p,n-i,r));

		}
		//r[n]=q;
		//return q;
	
	r[n]=q;
    return q;
	}
}
int memorized(int p[],int n)
{
	int *r=new int[n+1];
	for(int i=0;i<n+1;++i)
		r[i]=inf;
	return memorized_cut_rod_aux(p,n,r);
}
int main()
{
	 const int size=9 ;
	int p[11]={0,1,5,8,9,10,17,17,20,24,30};
	int sum=memorized(p,size);
	cout<<sum<<endl;
	system("pause");
	return 0;
}

算法导论第十五章之钢条切割问题（自顶向下法）