Understanding the bottom-up rod cut implementation

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.

8
задан nbro 18 November 2016 в 17:04
поделиться