algorithm - 动态规划 - 切杆自下而上算法 (CLRS) 解不正确？

Question

对于“切杆”问题:

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. [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 的“最后一段”没有被进一步切割，但长度为 j-i 的剩余部分被切割。

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

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