Понимание реализации реза снизу вверх

Question

In Введение в алгоритмы (CLRS) , Cormen et al. поговорим о решении задачи резки стержня следующим образом (стр. 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 и s[i], что дает нам оптимальный размер для отрезания первой части.

Мой вопрос касается внешнего цикла, который повторяет j с 1 до n, и внутреннего цикла i, который также идет от 1 до n.

В строке 6 мы сравниваем q (максимальный доход, полученный на данный момент) с r[j - i], максимальным доходом, полученным в ходе предыдущего сокращения.

Когда j = 1 and i = 1, кажется, все в порядке, но самая следующая итерация внутреннего цикла, где j = 1 and i = 2, не будет r[j - i] be r[1 - 2] = r[-1]?

Я не уверен, имеет ли здесь значение отрицательный индекс. Это опечатка в CLRS или я что-то здесь упускаю?

В случае, если некоторые из вас не знают, в чем заключается проблема с резанием удочек, вот пример .

Answer 1

Вот ключ: for i = 1 to j

i начинается с 1 и увеличивается в значении до значения j.

i никогда не будет больше j, поэтому j-i никогда не будет меньше нуля.

Answer 2

Вам не хватает условий во внутреннем цикле for.В этом значение i идет только до j.Таким образом, если он превышает j, цикл будет прерван.Отсюда нет вопроса об отрицательных показателях, которые вы упомянули.

Answer 3

Переменная i не будет больше переменной j из-за внутреннего цикла, поэтому индекс r никогда не станет меньше нуля.