Comprensión de la implementación de corte de varilla ascendente

Question

En Introduction to Algorithms(CLRS), Cormen et al. hablar sobre la solución del problema Rod-corte, como sigue (página 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 

Aquí p[i] es el precio de corte de la varilla a la longitud i, r[i] es el ingreso de cortar la varilla al fin, y s[i], nos da el tamaño óptimo para la primera pieza para cortar.

Mi pregunta es sobre el bucle exterior que itera j1-n y el bucle interior i que va 1-n también.

En la línea 6 estamos comparando q (la ganancia máxima obtenida hasta ahora) con r[j - i], el ingreso máximo ganado durante el corte anterior.

Cuando j = 1 and i = 1, parece estar bien, pero la próxima iteración del lazo interno donde j = 1 and i = 2, ¿no r[j - i] be r[1 - 2] = r[-1]?

No estoy seguro si el índice negativo tiene sentido aquí. ¿Eso es un error tipográfico en CLRS o me falta algo aquí?

I caso de que algunos de ustedes no saben cuál es el problema de corte de varilla, aquí hay un example.

Answer 1

Aquí está la clave: for i = 1 to j

i comenzará a la 1 y aumentar su valor hasta, pero sin exceder el valor dej.

i nunca será mayor que j, por lo tanto, j-i nunca será inferior a cero.

Answer 2

Variable No seré mayor que la variable j debido a que el bucle interno y, por lo tanto, el índice r nunca será inferior a cero.

Answer 3

Faltan las condiciones en el ciclo for interno. En eso, el valor de i va solo hasta j. Entonces, si excede j, el ciclo terminará. Por lo tanto, no hay duda de los índices negativos que mencionaste.