了解自下而上的杆切割实施

In 算法导论(CLRS) https://rads.stackoverflow.com/amzn/click/com/0262033844，科门等人。下面谈谈解决切棒问题（第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

Here p[i]是切割长度为 i 的杆的价格，r[i]是切割长度为 i 的杆的收入，s[i]，为我们提供了第一块要切割的最佳尺寸。

我的问题是关于迭代的外循环j from 1 to n和内循环i那来自1 to n以及。

在第 6 行我们正在比较q（迄今为止获得的最大收入）r[j - i]，上次削减期间获得的最大收入。

When j = 1 and i = 1，看起来没问题，但是内循环的下一次迭代在哪里j = 1 and i = 2, won't r[j - i] be r[1 - 2] = r[-1]?

我不确定负指数在这里是否有意义。这是 CLRS 中的拼写错误还是我在这里遗漏了一些东西？

我发现你们中的一些人不知道杆切割问题是什么，这是一个example http://www.columbia.edu/~cs2035/courses/csor4231.F09/dynamic.pdf.

关键是：for i = 1 to j

i将从 1 开始并增加值最多但不超过的价值j.

i永远不会大于j, thus j-i永远不会小于零。