钢条切割

public class CUTROD
{
　　　　　//1.自顶向下
    public static int Memoized_Cut_Rod(int []p,int n)
    {
        int r[]=new int[n+1];
        for(int i=0;i<r.length;i++)
        {
            r[i]=Integer.MIN_VALUE;
        }
        return Memorized_Cut_Rod_Aux(p,n,r);
        
    }
    private static int Memorized_Cut_Rod_Aux(int[] p, int n, int[] r)
    {
        int q=0;
        if(r[n]>=0)
            return r[n];
        if(n==0)
            q=0;
        else
        {
            q=Integer.MIN_VALUE;
            //i表示左边的长度，n-i表示剩余的长度
            for(int i=1;i<=n;i++)
            {
                //当前的效益是 当前钢筋长度的效益与剩余钢筋长度的效益的和
                //要求的是最大值，所以是每次求出的最大值用q保存，依次递归计算求出最大值
                q=Math.max(q, p[i-1]+Memorized_Cut_Rod_Aux(p,n-i,r));
            }
            //为了避免重复计算，使用r[n]保存当前的最大效益，下次再算长度为n的效益时，直接根据下标取出来
            r[n]=q;
        }
        
        return q;
    }
    //2.自底向上
    public static int Bottom_Up_Cut_Rod(int[]p,int n)
    {
        //初始化n+1个数组长度，因为要存r[0]
        int []r=new int[n+1];
        //设置r[0]=0,因为长度为0的钢筋效益为0
        r[0]=0;
        int q;
        //左边的长度从1到n，依次求解
        for(int j=1;j<=n;j++)
        {
            //q保存当前长度的最大值
            q=Integer.MIN_VALUE;
            //自底向上求解，从长度为1的开始，这样每次求出的都是长度小于j的最优值，
            //由于我们每次都保存了长度为j的最大值，所以p[i-1]+r[j-i]是求长度为i的效益，而
            //r[j-i]已经保存，因此指数解降为多项式解
            for(int i=1;i<=j;i++)
                q=Math.max(q, p[i-1]+r[j-i]);
            //保存长度为j的最优效益
            r[j]=q;
        }
        return r[n];
    }
public static int Extended_Bottom_Cut_Rod(int []p,int n,int []r,int []s)
    {
        r[0]=0;
        int q=0;
        for(int j=1;j<=n;j++)
        {
            q=Integer.MIN_VALUE;
            for(int i=1;i<=j;i++)
            {
                if(q<p[i-1]+r[j-i])
                {
                    q=p[i-1]+r[j-i];
                    s[j]=i;
                }
                r[j]=q;
            }
        }
        return q;
    }
    public static void Print_Cut_Rod_Solution(int[]p,int n)
    {
        int[]r=new int[n+1];
        int[]s=new int[n+1];
        int q=Extended_Bottom_Cut_Rod(p,n,r,s);
        System.out.println(q);
        while(n>0)
        {
            System.out.print(s[n]+" ");
            n=n-s[n];
        }
    }
    public static void main(String[] args)
    {
        int []p={1,5,8,9,10,17,17,20,24,30};
        System.out.println(Memoized_Cut_Rod(p,4));
        
    }
}