Burst Balloons
Se te da una fila de globos como nums, donde nums[i] es el número del globo i. Los revientas todos, uno a la vez, en cualquier orden. Reventar un globo te da left × nums[i] × right monedas, donde left y right son los números de sus vecinos actuales, los globos más cercanos que aún permanecen en la fila a cada lado. Si falta un vecino, cuenta como 1. Después de reventar un globo, sus dos vecinos pasan a ser adyacentes. Devuelve la mayor cantidad de monedas que puedas obtener.
Función
- numsinteger-array
- los números de los globos, de izquierda a derecha
- Devuelveinteger
- la mayor cantidad de monedas que puedes conseguir al reventar todos los globos
Restricciones
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100- La respuesta es menor que 3 × 108, así que cabe en un entero con signo de 32 bits.
Ejemplos
- Entrada
- nums = [2, 4, 3]
- Salida
- 33
- Explicación
- Descompón el 4 para obtener 2 × 4 × 3 = 24. El 2, ahora junto al 3, suma 1 × 2 × 3 = 6, y el 3 suma 3: 33 en total.
- Entrada
- nums = [6, 1, 2, 5]
- Salida
- 108
- Explicación
- Revienta el 1 (6 × 1 × 2 = 12), después el 2, ahora entre 6 y 5 (6 × 2 × 5 = 60), después el 5 para obtener 30 y el 6 para obtener 6: 108 en total.
- Entrada
- nums = [8]
- Salida
- 8
- Explicación
- El único globo no tiene vecinos, y cada vecino que falta cuenta como 1, así que obtiene 1 × 8 × 1 = 8.
Para ir más allá
¿También puedes devolver un orden de explosión que consiga la mayor cantidad de monedas?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Supón que decides qué globo reventar primero. Sus dos vecinos pasan a ser adyacentes, así que los globos a su izquierda y los globos a su derecha siguen afectándose entre sí. ¿Puedes dividir el problema de esa manera en dos problemas más pequeños?
Invierte la pregunta y elige el globo que estalla al final de un tramo. Hasta entonces permanece inmóvil, como una pared, así que los globos a su izquierda y a su derecha nunca se convierten en vecinos. Cuando finalmente estalla, sus vecinos son los dos globos que limitan el tramo.
Coloca un 1 en ambos extremos de
nums. Seabest[left][right]la mayor cantidad de monedas que se puede obtener de los globos que están estrictamente entre las posicionesleftyright. Prueba cada globokentre ellos como el último: se obtienenbest[left][k] + best[k][right]másvals[left] × vals[k] × vals[right]. Completa primero los intervalos cortos y luego los largos.
Solución
Cada explosión cambia quién queda junto a quién, así que el primer globo que explotas no divide la fila: sus dos lados se convierten en vecinos. El último globo que explotas en un tramo sí lo hace. Permanece mientras todo lo demás desaparece, así que los tramos a sus dos lados son independientes, y una tabla de intervalos sobre los tramos resuelve el problema en O(n³).
Prueba todos los órdenes de estallido
Correcto, pero no termina con las pruebas más grandes
Intuición
Elige un globo, suma left × value × right, elimínalo y resuelve la fila más corta de la misma manera, conservando el mejor total entre todas las opciones. Prueba todos los órdenes, así que es correcto.
La primera explosión tiene n opciones, la siguiente n-1, y así sucesivamente: n! órdenes, que ya son 479,001,600 para 12 globos. Recordar los resultados para cada conjunto de globos que quedan en pie no ayuda, ya que hay 2^n conjuntos.
Algoritmo
- Escribe
burstAll(row), que devuelve la mayor cantidad de monedas de los globos derow, o 0 si la fila está vacía. - Para cada posición
k, ganaleft × row[k] × right, usando 1 más allá de cualquiera de los extremos, másburstAllde la fila sinrow[k]. - Devuelve el mejor total entre todos los valores de
ky llama aburstAll(nums).
def maxCoins(nums):
# Most coins you can still collect from the balloons in row
def burst_all(row):
top = 0
for k in range(len(row)):
left = row[k - 1] if k > 0 else 1
right = row[k + 1] if k + 1 < len(row) else 1
# Burst row[k] now, then do as well as possible with the rest
coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
top = max(top, coins)
return top
return burst_all(nums)Recursión en el último globo, con un recordatorio
Intuición
Completa la fila con un 1 en cada extremo: vals = [1] + nums + [1]. Los rellenos nunca estallan y ocupan el lugar de los vecinos que faltan. Sea solve(left, right) la cantidad máxima de monedas que se obtiene con los globos estrictamente entre dos posiciones ocupadas.
Supongamos que k estalla al final dentro de ese intervalo. Todos los demás globos del intervalo estallan mientras k permanece como una pared, así que la parte entre left y k solo tiene sus propios globos y dos bordes fijos, y lo mismo ocurre con la parte entre k y right. Cuando k estalla, sus vecinos son exactamente left y right. Por tanto, el mejor resultado para el intervalo es, para cada k, el mejor resultado de las dos partes más vals[left] × vals[k] × vals[right]. La respuesta corresponde al intervalo entre los dos rellenos. Hay aproximadamente n²/2 intervalos y cada uno prueba hasta n globos, así que la memorización reduce la complejidad a O(n³).
Algoritmo
- Construye
valscomonumscon un 1 añadido en cada extremo, y establecemcomo su longitud. - Crea una memo de
m × mllena de -1. - Escribe
solve(left, right): devuelve 0 siright - left < 2, y el valor almacenado si lo hay. - De lo contrario, prueba cada
kestrictamente entre ellos como el último globo, conserva el mayor valor desolve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right]y almacénalo. - Devuelve
solve(0, m-1).
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
memo = [[-1] * m for _ in range(m)]
# Most coins from the balloons strictly between left and right
def solve(left, right):
if right - left < 2:
return 0
if memo[left][right] >= 0:
return memo[left][right]
top = 0
for last in range(left + 1, right):
# last bursts after every other balloon in the gap
coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
top = max(top, coins)
memo[left][right] = top
return top
return solve(0, m - 1)Completa la tabla de intervalos por anchura
Intuición
La recursión solo pregunta por intervalos más estrechos, así que completa la misma tabla con bucles, primero los intervalos estrechos y luego los amplios. Después, best[left][k] y best[k][right] ya tienen sus valores finales cuando los necesita un intervalo más amplio.
Para [2, 4, 3], ampliado a [1, 2, 4, 3, 1], best[0][4] prueba cada globo como último. Si el 3 es el último, se obtiene best[0][3] = 30 más 1 × 3 × 1, para un total de 33, el mejor resultado de los tres.
El trabajo coincide con el de la versión con memoización, pero los bucles simples evitan millones de llamadas a funciones, lo que hace que esta versión sea varias veces más rápida en un lenguaje como Python o R.
Algoritmo
- Construye
valscomonums, añadiendo un 1 en cada extremo, y establecemcomo su longitud. - Crea una tabla
m × mbestrellenada con 0. - Para cada ancho de 2 a
m-1, y cadaleftconright = left + widthdentro del arreglo, prueba cadakestrictamente entre ellos. - Establece
best[left][right]como el mayor valor entrebest[left][k] + best[k][right] + vals[left] × vals[k] × vals[right]. - Devuelve
best[0][m-1].
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
# best[left][right]: most coins from the balloons strictly between left and right
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
edge = vals[left] * vals[right]
top = 0
for last in range(left + 1, right):
# last goes after every other balloon in the gap,
# so left and right are its neighbours when it bursts
coins = best[left][last] + best[last][right] + edge * vals[last]
if coins > top:
top = coins
best[left][right] = top
return best[0][m - 1]
Errores comunes y casos límite
- Dividir según el primer estallido, usando sus vecinos originales,
nums[k-1] × nums[k] × nums[k+1]más los dos lados. Esos vecinos quizá ya hayan desaparecido: con[2, 4, 3]informa 44, más de lo que obtiene cualquier orden real. - Rellenar la tabla fila por fila, aumentando
left. Después,best[k][right]parak > leftaún no se ha calculado y se lee como 0. Rellénala por anchura o recorreleften orden descendente. - Marcar con 0 un intervalo sin resolver en la memoización. Un intervalo de globos con valor cero realmente vale 0, así que se vuelve a resolver en cada visita. Usa -1.
- En Lua y R, las posiciones con relleno van de 1 a
m, así que la respuesta esbest[1][m].
Preguntas frecuentes3
¿Por qué Burst Balloons elige el último globo en lugar del primero?
Después de la primera explosión, sus dos lados se convierten en vecinos, así que siguen afectándose entre sí. El último globo de un tramo permanece mientras los demás explotan, así que sus dos lados nunca se encuentran y cada uno es un subproblema independiente. Cuando explota, sus vecinos son los límites del tramo.
¿Cuál es la complejidad temporal de Burst Balloons?
Tiempo O(n³) y memoria O(n²): aproximadamente n²/2 intervalos, cada uno probando hasta n globos como el último. Para 300 globos, eso equivale a unos 4.5 × 10^6 pasos. Probar todos los órdenes es O(n · n!).
¿Se puede resolver el problema de reventar globos con un orden voraz?
No. Reventar primero el globo más pequeño da 24 con [2, 4, 3], donde es posible obtener 33. Reventar el globo que más paga en ese momento da 42 con [2, 9, 2], donde reventar primero un 2 da 18 + 18 + 9 = 45. Cada globo que revientas cambia el precio de los siguientes.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def maxCoins(nums):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
nums = [2, 4, 3]
Salida Esperada
33