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

Question

对于"rod cutting"问题：

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 方法背后的直觉是，他们试图找到单个 "last cut"，假设最后一根杆的长度为 i，因此其值恰好为 p[i] .在这个公式中，长度 i 的 "last piece" 没有被进一步切割，但长度 j-i 的剩余部分被切割。

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

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

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)

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

Dynamic Programming - Rod Cutting Bottom Up Algorithm (CLRS) Solution Incorrect?

algorithm

memoization

dynamic-programming

bottom-up