Burst Balloons: PD por intervalos en sentido inverso

Dadas n globos con valores nums, reventar el globo i proporciona nums[i-1] * nums[i] * nums[i+1] monedas (el producto de su propio valor y el de sus vecinos actuales). Después de reventarlo, sus vecinos pasan a ser adyacentes. Encuentre el máximo de monedas que puede obtener al reventar todos los globos. La simulación ingenua es difícil porque reventar un globo cambia los vecinos; la DP de intervalos en sentido inverso evita elegantemente esta dificultad.

Si intentamos definir dp[i][j] como el máximo de monedas obtenido al reventar los globos del intervalo [i, j] y pensamos en qué globo reventar primero, nos encontramos con un problema: reventar primero el globo k implica que nums[k-1] y nums[k+1] deben ser sus vecinos actuales, pero esos globos podrían reventarse después, lo que cambiaría los vecinos dinámicamente. El estado es difícil de definir claramente en la dirección hacia delante.

El truco consiste en pensar en qué globo será el último en reventarse dentro del intervalo [i, j]. Cuando el globo k es el último en reventarse en [i, j], todos los demás globos de [i, j] ya han desaparecido. Por lo tanto, los vecinos del globo k son exactamente nums[i-1] y nums[j+1]: los globos frontera situados justo fuera del intervalo. Esto hace que el cálculo de monedas del último reventado sea determinista: no depende del orden de los reventados anteriores.

Añada globos centinela: anteponga y añada 1 a nums para formar nums = [1] + nums + [1]. Defina dp[i][j] como el máximo de monedas obtenido al reventar todos los globos situados estrictamente entre los índices i y j (exclusivos), donde nums[i] y nums[j] son los globos frontera que permanecen. Recurrencia: para cada posible último globo k en (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Rellenamos el arreglo con centinelas, inicializamos la tabla de DP con ceros (un intervalo vacío equivale a 0 monedas) y la rellenamos aumentando la longitud de los intervalos. La respuesta final es dp[0][n+1], que representa el máximo de monedas obtenido al reventar todos los globos originales, con los centinelas como fronteras permanentes.

Para [3, 1, 5, 8], rellenado con centinelas para obtener [1, 3, 1, 5, 8, 1] (índices del 0 al 5). Queremos dp[0][5]. Para intervalos de longitud 2 (un globo en el interior): dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40. Al avanzar, la solución óptima consiste en reventar el 1 en último lugar entre {3,1,5,8}, después de reventar primero sus vecinos, lo que produce un total de 167 monedas.

Hay O(n²) intervalos y, para cada intervalo, probamos O(n) puntos de división, lo que da una complejidad temporal de O(n³). El espacio es O(n²) para la tabla de DP. Para n = 500 globos, esto supone 125 millones de operaciones, una cantidad viable para las restricciones de una entrevista. El relleno con centinelas simplifica la gestión de los límites: sin él, tendría que comprobar explícitamente si i-1 y j+1 están dentro de los límites.

La misma solución puede escribirse de arriba abajo con @lru_cache, lo que puede resultar más intuitivo de deducir durante una entrevista. Defina solve(i, j) como el máximo de monedas en el intervalo abierto (i, j). La función prueba todos los valores de k como último globo reventado y memoriza los resultados. Ambos enfoques tienen la misma complejidad temporal y espacial.

Un error común consiste en definir dp[i][j] como las monedas obtenidas cuando se revienta el primer globo de [i,j], en lugar del último. Esto falla porque el cálculo de monedas del primer reventado depende de globos vecinos que todavía no se han reventado, y el estado de esos vecinos cambia a medida que avanza el algoritmo. Piense siempre en el último elemento en la DP de intervalos cuando los límites dependen de los elementos restantes.

Se eligen centinelas con valor 1 porque actúan como elementos neutros de la multiplicación. Cuando un globo frontera es el último en reventarse, el valor de sus monedas es boundary * last * boundary = 1 * last * 1 = last. Usar 0 produciría 0 monedas (incorrecto), mientras que usar otros valores distorsionaría el cálculo. El truco de los centinelas unifica claramente todos los casos de frontera sin tener que tratar de forma especial los globos situados en los extremos izquierdo y derecho.

En la DP de intervalos estándar (multiplicación de cadenas de matrices), el punto de división k representa el lugar donde dividimos el problema en dos subproblemas resueltos de forma independiente. En Burst Balloons, k es el último globo en reventarse del intervalo, lo que hace que los dos subintervalos [i,k] y [k,j] sean independientes, dado que k sigue presente como frontera. Esta perspectiva inversa es la idea creativa que permite resolver Burst Balloons mediante DP de intervalos.

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

En esta lección ha aprendido: la simulación hacia delante falla porque hacer explotar globos cambia los vecinos de forma impredecible, la idea inversa define k como el último globo que explota en un intervalo, lo que convierte a los vecinos en nums[i] y nums[j], y la recurrencia dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) con relleno de centinelas proporciona una solución O(n³). A continuación pasaremos a la programación dinámica de la mochila, empezando por la mochila clásica 0/1 y su optimización espacial.