Patrón de PD por intervalos y orden de llenado

La DP de intervalos es un patrón de programación dinámica en el que el estado dp[i][j] representa la respuesta óptima para el subproblema que abarca los índices i a j. La idea clave es resolver primero los intervalos más pequeños y ampliar progresivamente la solución hasta cubrir todo el rango. Este patrón modela de forma natural problemas como la multiplicación de cadenas de matrices, la partición de palíndromos y el reventado de globos, en los que los límites del subproblema son los extremos izquierdo y derecho de un rango.

En la DP de intervalos, el estado es dp[i][j], donde i <= j. Los casos base son los intervalos de un solo elemento: dp[i][i]. Se resuelven trivialmente; por ejemplo, una sola matriz tiene un coste de multiplicación igual a cero. Los intervalos de dos elementos, dp[i][i+1], también suelen tener respuestas sencillas. Rellenamos la tabla con longitudes de intervalo crecientes, desde la longitud 1 hasta n.

El detalle fundamental de la DP de intervalos es el orden de llenado. Debemos calcular todos los intervalos de longitud L antes de calcular los intervalos de longitud L+1, porque un intervalo más largo depende de subintervalos más cortos. El bucle externo recorre la longitud del intervalo de 2 a n; el bucle intermedio establece el límite izquierdo i; y deducimos el límite derecho mediante j = i + L - 1.

El problema clásico de DP de intervalos es la multiplicación de cadenas de matrices: dadas matrices con dimensiones dims[0..n], encuentre el número mínimo de multiplicaciones escalares necesarias para calcular el producto. Multiplicar la matriz A(p×q) por la matriz B(q×r) cuesta p*q*r operaciones. dp[i][j] = coste mínimo de multiplicar las matrices desde i hasta j. El punto de división k determina dónde se divide la secuencia en dos subcadenas.

Recorramos el ejemplo de la cadena de matrices con las dimensiones [10, 30, 5, 60], que representa tres matrices: A(10×30), B(30×5) y C(5×60). Para dp[0][2], probamos la división en k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, y en k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Por tanto, dp[0][2] = 4500, que se obtiene multiplicando AB primero.

Al calcular dp[i][j], consultamos dp[i][k] y dp[k+1][j] para todos los valores de k en [i, j-1]. Ambos subintervalos tienen una longitud estrictamente menor que [i, j]. Al recorrer las longitudes de menor a mayor, todos los subintervalos necesarios se calculan antes de necesitarlos. Este es el argumento fundamental de corrección del orden de llenado de la DP de intervalos: los intervalos más cortos siempre son dependencias de los más largos.

Como alternativa, la DP de intervalos se puede implementar de arriba abajo con memoización. Escribimos una función recursiva solve(i, j) que devuelve el coste óptimo del intervalo [i, j] y guardamos los resultados en un diccionario. La recursión gestiona automáticamente el orden de llenado. El enfoque de arriba abajo suele ser más fácil de razonar, pero puede tener sobrecarga por las llamadas a funciones; el enfoque de abajo arriba es más rápido en la práctica para entradas grandes.

La DP de intervalos tiene O(n²) estados (todos los pares (i, j)) y cada estado recorre O(n) puntos de división, lo que da un total de O(n³) de tiempo. El espacio es O(n²) para la tabla de DP. Para la multiplicación de cadenas de 100 matrices, esto supone 1.000.000 de operaciones, una cantidad perfectamente viable. El patrón aparece en muchos problemas difíciles de LeetCode y es uno de los favoritos en las entrevistas de FAANG debido a su estructura poco evidente.

Para reconstruir la parentización real (no solo el coste), guarde una tabla independiente split[i][j] que registre qué valor de k consiguió el mínimo en cada estado. Después, lea las divisiones recursivamente: reconstruct(i, j) muestra la agrupación óptima recurriendo sobre [i, split[i][j]] y [split[i][j]+1, j]. Esta técnica se aplica a todos los problemas de DP de intervalos.

La plantilla universal de DP de intervalos consta de tres partes: (1) inicializar los casos base para elementos individuales; (2) recorrer longitudes crecientes y, para cada longitud, recorrer los límites izquierdos válidos calculando el límite derecho; y (3) para cada intervalo, recorrer todos los puntos de división y aplicar la recurrencia específica del problema. Lo único que cambia entre problemas es la fórmula de recurrencia dentro del bucle más interno.

Entre los problemas que utilizan DP de intervalos se incluyen: Multiplicación de cadenas de matrices (minimizar operaciones), Reventar globos (maximizar monedas), Impresora extraña (minimizar operaciones de impresión), Triangulación de un polígono con puntuación mínima y Partición de palíndromos II. Todos utilizan la misma estructura de orden de llenado, pero con recurrencias diferentes. Reconozca el patrón cuando un problema solicite un valor óptimo sobre un rango o una secuencia que se pueda dividir en cualquier punto interior.

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección ha aprendido que: la DP de intervalos utiliza dp[i][j] para representar la respuesta óptima sobre un rango; el orden de llenado debe seguir longitudes de intervalo crecientes para calcular primero los subintervalos; y la plantilla universal tiene una complejidad temporal de O(n³) y espacial de O(n²). A continuación exploraremos la subsecuencia y la subcadena palindrómicas más largas utilizando este mismo patrón.