动态编程 - 杆切割自下而上算法（CLRS）解决方案不正确？

Question

对于“杆切割”问题：

给定一根长度为n英寸的杆和一系列价格，其中包含所有尺寸小于n的尺寸的价格。确定通过切割杆和销售件可获得的最大值。 [link]

算法简介（CLRS）第366页给出了自下而上（动态编程）方法的伪代码：

1. BOTTOM-UP-CUT-ROD(p, n)              
2. let r[0 to n]be a new array .        
3. r[0] = 0                             
4. for j = 1 to n                       
5.     q = -infinity                    
6.     for i = 1 to j                   
7.         q = max(q, p[i] + r[j - i])  
8.     r[j] = q                         
9. return r[n]                          

现在，我无法理解第6行背后的逻辑。为什么他们在做max(q, p[i] + r[j - i])而不是max(q, r[i] + r[j - i])？因为，这是一个自下而上的方法，我们先计算r[1]，然后再计算r[2], r[3]...。这意味着在计算r [x]时，我们保证有r [x - 1]。

r [x]表示我们可以获得长度为x的杆的最大值（在将其切割为最大化利润之后），而p [x]表示长度为x的单根杆的价格。第3 - 8行计算j = 1到n的值r[j]，第5 - 6行计算通过考虑所有可能的切割我们可以卖出长度为j的棒的最大价格。那么，如何在第6行使用p [i]代替r [i]是有意义的。如果在我们切割长度= i后试图找到杆的最大价格，我们不应该添加价格r [i]和r [j - 1]？

我已经用这个逻辑编写了一个Java代码，它似乎为我尝试过的一些测试用例提供了正确的输出。我错过了一些我的代码产生错误/低效解决方案的情况吗？请帮帮我。谢谢！

class Solution {
    private static int cost(int[] prices, int n) {
        if (n == 0) {
            return 0;
        }

        int[] maxPrice = new int[n];

        for (int i = 0; i < n; i++) {
            maxPrice[i] = -1;
        }

        for (int i = 1; i <= n; i++) {
            int q = Integer.MIN_VALUE;

            if (i <= prices.length) {
                q = prices[i - 1];
            }

            for (int j = i - 1; j >= (n / 2); j--) {
                q = Math.max(q, maxPrice[j - 1] + maxPrice[i - j - 1]);
            }

            maxPrice[i - 1] = q;
        }

        return maxPrice[n - 1];
    }


    public static void main(String[] args) {
       int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};

        System.out.println(cost(prices, 8));
    }
}

Answer 1

它们应该是等价的。

CLRS方法背后的直觉是他们试图找到单一的“最后一次切割”，假设最后一根杆具有长度i，因此具有恰好p[i]的值。在这个公式中，长度为i的“最后一块”没有进一步切割，但长度j-i的剩余部分是。

您的方法将杆的所有分裂视为两个部分，其中两个部分中的每一个都可以进一步切割。与CLRS方法相比，这考虑了案例的超集。

两种方法都是正确的，具有相同的渐近复杂度。但是，我认为CLRS解决方案更“规范”，因为它更接近于一种常见形式的DP解决方案，您只考虑最后一个“事物”（在这种情况下，最后一块未切割的杆）。

Answer 2

我想这两种方法都是正确的。

在我们证明它们都是正确的之前，我们先定义每种方法的确切作用

p [i] + r [j - i]将为您提供从长度为j的杆中获得的最大值，并且该块的大小为“i”（不能将该块进一步分割）

r [i] + r [j-i]将为您提供从长度为i的杆获得的最大值，并且第一次切割的长度为“i”（可以进一步分割两个部分）

现在考虑我们有一根长度为X的杆，解决方案组将包含一段长度k

由于k是0 <k <X，你会发现第一种方法中p [k] + r [X-k]的最大值

在第二种方法中，你可以用r [k] + r [X-k]找到相同的结果，因为我们知道r [k]将> = p [k]

但是你接近你可以更快地得到结果（一半的时间），因为你从两端切割杆，所以在接近你可以运行内环的一半长度应该是好的。

但我认为在你的代码中，内部for循环中存在一个错误，它应该是j> =（i / 2）而不是j> =（n / 2）