algorithm - 了解自下而上的切杆实现

Question

在Introduction to Algorithms(CLRS) , Cormen 等人。下面谈谈求解Rod-cutting问题(第369页)

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    let r[0...n] and s[0....n] be new arrays
    r[0] = 0

    for j = 1 to n:
        q = -infinity   

        for i = 1 to j:
            if q < p[i] + r[j - i]:  // (6)
                q = p[i] + r[j - i]
                s[j] = i
        r[j] = q

    return r and s

这里p[i]是切割长度为i的价格，r[i]是切割长度为i的 yield ， >s[i]，为我们提供了第一 block 要切断的最佳尺寸。

我的问题是关于将 j 从 1 迭代到 n 的外循环和内循环 i也从 1 到 n。

在第 6 行，我们将 q(目前获得的最大收入)与 r[j - i] 进行比较，r[j - i] 是上一次切割期间获得的最大收入。

当 j = 1 and i = 1 时，它似乎没问题，但是紧接着 j = 1 and i = 2 的内循环的下一次迭代， r[j - i] 不会是 r[1 - 2] = r[-1] 吗？

我不确定负索引在这里是否有意义。这是 CLRS 中的拼写错误还是我在这里遗漏了什么？

我想你们中有些人不知道切杆问题是什么，这里是 example .

Answer 1

这是关键:for i = 1 to j

i 将从 1 开始增加值直到但不超过 j 的值。

i 永远不会大于 j，因此 j-i 永远不会小于零。