¿Cuál es la justificación rigurosa de la exactitud de la segunda formulación de la solución DP de corte de varillas en CLRS?

Bueno, “riguroso” no es tan fácil de lograr publicar en Quora con un teléfono, pero veamos qué podemos hacer. Si miras la nota al pie un par de páginas antes, hay una simetría en el corte de varillas basada en la conmutatividad de la adición. La programación dinámica siempre trata de evitar hacer el mismo cálculo dos veces, por lo que nos importa la simetría.

Para mí, ambos son bastante intuitivos, ya que la primera ecuación dice “para cada corte posible, incluido el trivial, tome el precio de la barra completa o tome los cortes al mejor precio de cada par posible después de un solo corte. ” Sin embargo, hay repetición allí, ya que para cada tamaño pido dos “cortes al mejor precio”, por lo que no estaría satisfecho.

La intuición para la segunda ecuación sería más como “Para cada corte posible, incluido el trivial, puedo obtener el precio de un trozo y luego obtener los mejores precios para el otro trozo”. No debería ser difícil demostrar que ambos están haciendo lo mismo (i = n obviamente está cubierto, r_1 = p_1, inducción hacia arriba), pero la sutileza radica en cómo solo tenemos que recurrir a r_n una vez por cada opción de corte en lugar de dos veces.