动态规划-切割钢条问题

钢条长度i的价格Pi表如下：

长度i    1    2   3   4   5   6   7   8   9   10
价格Pi    1   5   8   9   10  17  17  20  24  30

钢条切割的最小单位是1，现给定一根钢条长度是X（1<=X<=10），怎么切割才能让收益最大？

 public static void main(String[] args) {
        //递归方案
        for (int i = 1; i <= 10; i++) {
            System.out.printf("钢条长度%d米， 最大收益%d， 计算了%d次， 最佳切割方案%s  \n", i, cut(i), loop, cutSolutions.get(i));
            loop = 0;
        }
        cutSolutions.clear();
        System.out.println("华丽的分割线==================");
        //动态规划
        for (int i = 1; i <= 10; i++) {
            System.out.printf("钢条长度%d米， 最大收益%d， 计算了%d次， 最佳切割方案%s  \n", i, cut2(i), loop, cutSolutions.get(i));
            loop = 0;
        }
    }

    static Map<Integer, Integer> priceMap = new HashMap<>();

    static {
        priceMap.put(1, 1);
        priceMap.put(2, 5);
        priceMap.put(3, 8);
        priceMap.put(4, 9);
        priceMap.put(5, 10);
        priceMap.put(6, 17);
        priceMap.put(7, 17);
        priceMap.put(8, 20);
        priceMap.put(9, 24);
        priceMap.put(10, 30);
    }

    private static Map<Integer, Integer> sumCache = new HashMap<>();
    private static Map<Integer, List<Integer>> cutSolutions = new HashMap<>();

    private static int loop = 0;

    private static int cut(int length) {
        if (length == 0) {
            return 0;
        }
        loop++;
        int sum = priceMap.get(length);
        for (int i = 1; i <= length; i++) {
            int tempSum = sum;
            sum = Math.max(sum, priceMap.get(i) + cut(length - i));
            if (sum > tempSum) {
                List<Integer> list = cutSolutions.containsKey(length) ? cutSolutions.get(length) : new ArrayList<>();
                list.clear();
                list.add(i);
                list.addAll(cutSolutions.get(length - i));
                cutSolutions.put(length, list);
            }
        }
        if(!cutSolutions.containsKey(length)){
            cutSolutions.put(length, Arrays.asList(length));
        }
        return sum;
    }

    private static int cut2(int length) {
        if (length == 0) {
            return 0;
        }
        loop++;
        int sum = priceMap.get(length);
        for (int i = 1; i <= length; i++) {
            int tempSum = sum;
            int remaining = length - i;
            sum = Math.max(sum, priceMap.get(i) + sumCache.computeIfAbsent(remaining, StealCut::cut2));
            if (sum > tempSum) {
                List<Integer> list = cutSolutions.containsKey(length) ? cutSolutions.get(length) : new ArrayList<>();
                list.clear();
                list.add(i);
                list.addAll(cutSolutions.get(remaining));
                cutSolutions.put(length, list);
            }
        }
        sumCache.put(length, sum);
        if(!cutSolutions.containsKey(length)){
            cutSolutions.put(length, Arrays.asList(length));
        }
        return sum;
    }

钢条长度1米， 最大收益1， 计算了1次， 最佳切割方案[1]  
钢条长度2米， 最大收益5， 计算了2次， 最佳切割方案[2]  
钢条长度3米， 最大收益8， 计算了4次， 最佳切割方案[3]  
钢条长度4米， 最大收益10， 计算了8次， 最佳切割方案[2, 2]  
钢条长度5米， 最大收益13， 计算了16次， 最佳切割方案[2, 3]  
钢条长度6米， 最大收益17， 计算了32次， 最佳切割方案[6]  
钢条长度7米， 最大收益18， 计算了64次， 最佳切割方案[1, 6]  
钢条长度8米， 最大收益22， 计算了128次， 最佳切割方案[2, 6]  
钢条长度9米， 最大收益25， 计算了256次， 最佳切割方案[3, 6]  
钢条长度10米， 最大收益30， 计算了512次， 最佳切割方案[10]  
华丽的分割线==================
钢条长度1米， 最大收益1， 计算了1次， 最佳切割方案[1]  
钢条长度2米， 最大收益5， 计算了1次， 最佳切割方案[2]  
钢条长度3米， 最大收益8， 计算了1次， 最佳切割方案[3]  
钢条长度4米， 最大收益10， 计算了1次， 最佳切割方案[2, 2]  
钢条长度5米， 最大收益13， 计算了1次， 最佳切割方案[2, 3]  
钢条长度6米， 最大收益17， 计算了1次， 最佳切割方案[6]  
钢条长度7米， 最大收益18， 计算了1次， 最佳切割方案[1, 6]  
钢条长度8米， 最大收益22， 计算了1次， 最佳切割方案[2, 6]  
钢条长度9米， 最大收益25， 计算了1次， 最佳切割方案[3, 6]  
钢条长度10米， 最大收益30， 计算了1次， 最佳切割方案[10]