用动态规划实现钢条切割问题

public class rodCutting {
    public static void main(String[] args){
        int[] input = {1,5,8,9,10,17,17,20,24,24};
        int result = rodCutting(input, input.length);
        System.out.println("最大收益"+result);
    }

    private static int rodCutting(int[] p, int n){
        //初始化
        int[] C = new int[n+1];
        int[] rec = new int[n+1];
        C[0] = 0;
        int q;
        //动态规划
        for(int j=1; j<=n; j++){//依次计算子问题
            //不切割钢条
            q = p[j-1];
            rec[j] = j;
            //枚举切割长度
            for(int i=1; i<=j-1; i++){
                //记录价格和切割的长度
                if(q<(p[i-1]+C[j-i])){
                    q = p[i-1]+C[j-i];
                    rec[j] = i;
                }
            }
            //记录子问题的解
            C[j] = q;
        }
        //追踪切割方案
        while(n>0){
            System.out.println(rec[n]);
            n = n-rec[n];
        }
        //返回最大值
        return C[p.length];
    }
}