Understanding the bottom-up rod cut implementation

Question

In Introduction to Algorithms(CLRS), Cormen et al. talk about solving the Rod-cutting problem as follows(page 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] is the price of cutting the rod at length i, r[i] is the revenue of cutting the rod at length i and s[i], gives us the optimal size for the first piece to cut off.

My question is about the outer loop that iterates j from 1 to n and the inner loop i that goes from 1 to n as well.

On line 6 we are comparing q (the maximum revenue gained so far) with r[j - i], the maximum revenue gained during the previous cut.

When j = 1 and i = 1, it seems to be fine, but the very next iteration of the inner loop where j = 1 and i = 2, won't r[j - i] be r[1 - 2] = r[-1]?

I am not sure if the negative index makes sense here. Is that a typo in CLRS or I am missing something here?

I case some of you don't know what the rod-cutting problem is, here's an example.

Unsigned Unsigned · Accepted Answer · 2011-03-31T22:51:07

Here's the key: for i = 1 to j

i will begin at 1 and increase in value up to but not exceeding the value of j.

i will never be greater than j, thus j-i will never be less than zero.

Understanding the bottom-up rod cut implementation

3 Answers