Burst Balloons

+10

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 el orden que quieras. 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 a cada lado que todavía están en la fila. Si falta un vecino, más allá de cualquiera de los extremos de la fila, cuenta como 1. Después de reventar un globo, sus dos vecinos pasan a ser adyacentes. Devuelve la mayor cantidad de monedas que puedes obtener.

Función

maxCoins(nums: integer-array) → integer

numsinteger-array: los números de los globos, de izquierda a derecha
Devuelveinteger: la mayor cantidad de monedas que puedes recoger al reventar todos los globos

Restricciones

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
La respuesta es menor que 3 × 10⁸, así que cabe en un entero con signo de 32 bits.

Ejemplos

Entrada: nums = [2, 4, 3]
Salida: 33
Explicación: Revienta primero los 4 para obtener 2 × 4 × 3 = 24 monedas. El 2 y el 3 ahora son vecinos, así que reventar el 2 te da 1 × 2 × 3 = 6, y el 3, ahora solo, da 1 × 3 × 1 = 3. Eso suma 33, y ningún otro orden lo supera: reventar primero el 2 pequeño ya te limita a 24.

+15 pruebas ocultas al enviar

Para ir más allá

¿También puedes devolver una orden explosiva que otorgue la mayor cantidad de monedas?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada ráfaga cambia qué globos están uno al lado del otro, así que una elección ahora cambia el costo de cada ráfaga posterior. Probar todos los órdenes implica n! secuencias. Pensar en el primer globo que explota tampoco divide la fila, porque sus dos lados pasan a ser vecinos. Pensar en el último globo que explota en un tramo sí lo hace: permanece en su sitio mientras todo lo demás desaparece, así que el tramo a su izquierda y el tramo a su derecha son independientes. Una tabla de intervalos sobre esos tramos resuelve el problema en O(n³).

Prueba todos los órdenes de explosión

Correcto, pero no termina con las pruebas más grandes

Intuición

Elige cualquier globo para reventarlo ahora, suma left × value × right usando sus vecinos actuales, quítalo de la fila y resuelve la fila más corta de la misma manera. Hazlo para cada opción y conserva el total más alto. Una función recursiva burstAll(row) hace exactamente esto. Explora todos los órdenes posibles, así que la respuesta es correcta.

Es inviable para tamaños reales. El primer estallido tiene n opciones, el segundo n-1, y así sucesivamente: n! órdenes. Para 12 globos, eso ya son 479,001,600 órdenes, y la prueba más grande tiene 120 globos. Recordar los resultados para cada conjunto de globos que aún sigue en pie no resuelve el problema, porque hay 2^n conjuntos de este tipo.

La solución es darse cuenta de por qué hay tantos subproblemas. Después de reventar el globo k, el globo de su izquierda y el de su derecha se tocan, así que lo que ocurre a la izquierda sigue dependiendo de la derecha. El siguiente enfoque elige el globo en el que centrarse de modo que los dos lados dejen de afectarse entre sí.

Algoritmo

Escribe burstAll(row), que devuelve la mayor cantidad de monedas de los globos de row.
Para cada posición k, lee los vecinos, usando 1 más allá de cada extremo.
Gana left × row[k] × right y suma el resultado de burstAll de la fila sin row[k].
Devuelve el mejor total de todos los k, o 0 si la fila está vacía.
Llama a burstAll(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 una nota

Intuición

Primero, pon un 1 en ambos extremos: vals = [1] + nums + [1]. Estos dos nunca estallan y representan a los vecinos que faltan en los bordes. Ahora fíjate en un intervalo entre dos posiciones left y right que siguen en pie, y pregúntate: ¿qué globo dentro del intervalo estalla al final?

Digamos que es k. Mientras estallan los demás globos del intervalo, k sigue ahí, de pie entre ellos como una pared. Todos los globos entre left y k tienen vecinos únicamente de ese tramo, con left y k como bordes fijos, y lo mismo ocurre entre k y right. Así que los dos tramos son problemas independientes del mismo tipo. Cuando k finalmente estalla, todo lo que había entre los bordes ha desaparecido, así que sus vecinos son exactamente left y right, y gana vals[left] × vals[k] × vals[right]. Elegir el primer globo no produce una división así, porque sus dos lados pasan a ser vecinos.

Esto da lugar a una recursión. solve(left, right) devuelve la mayor cantidad de monedas que se obtiene de los globos situados estrictamente entre left y right: 0 cuando el intervalo está vacío; en caso contrario, el mayor valor de solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] para cada k del intervalo. La respuesta es solve(0, m-1), el intervalo entre los dos topes.

Por sí sola, la recursión vuelve a resolver el mismo intervalo una y otra vez, así que guarda cada resultado en una tabla memo[left][right] y devuélvelo en la siguiente visita. Hay aproximadamente n²/2 intervalos, y cada uno prueba hasta n globos, por lo que el trabajo es O(n³). Usa -1 para un intervalo que aún no se ha resuelto, porque 0 es una respuesta válida. La recursión nunca tiene más de n+1 llamadas de profundidad, ya que cada llamada trabaja con un intervalo más estrecho.

Algoritmo

Construye vals como nums con un 1 añadido en cada extremo, y establece m como su longitud.
Crea una tabla de memorización de m × m rellena con -1.
Escribe solve(left, right): devuelve 0 si right - left < 2, y el valor almacenado si existe.
De lo contrario, prueba cada k estrictamente entre ellos como el último globo, conserva el mayor valor de solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] y guárdalo.
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)

Rellena la tabla de intervalos por anchura

Intuición

La recursión solo pregunta por intervalos más estrechos. Así que puedes rellenar la misma tabla sin recurrir a la recursión, siempre que rellenes los intervalos estrechos antes que los anchos. Sea best[left][right] la cantidad máxima de monedas de los globos estrictamente entre left y right, 0 si no hay nada en el intervalo. Para cada ancho, desde 2 en adelante, y cada intervalo de ese ancho, prueba cada k del interior como el último globo. best[left][k] y best[k][right] son más estrechos, así que sus valores ya son definitivos.

Toma [2, 4, 3]. Con los valores de relleno, queda vals = [1, 2, 4, 3, 1] en las posiciones de 0 a 4, y la respuesta es best[0][4]. Rellena los intervalos desde el más estrecho hasta el más ancho:

Ancho 2, un globo en el interior: best[0][2] = 1 × 2 × 4 = 8, best[1][3] = 2 × 4 × 3 = 24, best[2][4] = 4 × 3 × 1 = 12.
best[0][3], globos 2 y 4: si el 2 va último, da 0 + 24 + 1 × 2 × 3 = 30; si el 4 va último, da 8 + 0 + 1 × 4 × 3 = 20. Así que da 30.
best[1][4], globos 4 y 3: si el 4 va último, da 0 + 12 + 2 × 4 × 1 = 20; si el 3 va último, da 24 + 0 + 2 × 3 × 1 = 30. Así que da 30.
best[0][4], los tres globos: si el 2 va último, da 0 + 30 + 1 × 2 × 1 = 32; si el 4 va último, da 8 + 12 + 1 × 4 × 1 = 24; si el 3 va último, da 30 + 0 + 1 × 3 × 1 = 33. Así que da 33.

Lee las opciones ganadoras en orden inverso y obtendrás este orden: el 3 va al final; antes de eso, el 2 es el último del tramo a su izquierda, y el 4 va primero. Es decir, 24 + 6 + 3 = 33.

El trabajo es el mismo que con la memorización: 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 pasos para 300 globos, y una tabla de 302 × 302 números. Los bucles simples evitan millones de llamadas a funciones, lo que hace que esta versión sea varias veces más rápida que la recursión en un lenguaje como Python o R.

Algoritmo

Construye vals como nums con un 1 añadido en cada extremo, y establece m en su longitud.
Crea una tabla m × m best rellenada con 0.
Para cada ancho de 2 a m-1, y cada left con right = left + width dentro del array, prueba cada k estrictamente entre ellos.
Establece best[left][right] en el mayor valor de best[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

Los errores habituales son un orden codicioso, una recursión en el primer estallido, un marcador de memorización incorrecto y una tabla rellenada en el orden equivocado.

Los órdenes codiciosos fallan. Estallar primero el globo más pequeño da 24 con [2, 4, 3] en lugar de 33, y estallar el globo que da más en ese momento da 42 con [2, 9, 2], mientras que estallar primero un 2 da 18 + 18 + 9 = 45.
Dividir según el primer estallido usando sus vecinos originales, nums[k-1] × nums[k] × nums[k+1] más los dos lados, cuenta vecinos que quizá ya hayan desaparecido. Con [2, 4, 3] da 44, más de lo que cualquier orden real puede dar.
Contar los bordes como parte del intervalo. left y right siguen en pie cuando se vacía el intervalo; solo estallan los globos que están estrictamente entre ellos.
Rellenar la tabla fila por fila haciendo que left aumente. Entonces best[k][right] para k > left aún no está calculado y se lee como 0. Rellena por anchura o recorre left en orden descendente.
Marcar con 0 un intervalo sin resolver en la tabla de memorización. Un intervalo lleno de globos con valor cero realmente vale 0, así que parece no estar resuelto para siempre y se vuelve a resolver en cada visita. Usa -1.
Olvidar los dos 1 de relleno, lo que deja a los globos de los extremos sin vecinos con los que multiplicarse.
En Lua y R, las posiciones rellenadas van de 1 a m, así que la respuesta es best[1][m].

Preguntas frecuentes4

¿Por qué Burst Balloons elige el último globo en lugar del primero?

Después del primer estallido, los globos a sus dos lados se convierten en vecinos, así que la parte izquierda y la parte derecha siguen afectándose entre sí y no se pueden resolver por separado. El último globo de un tramo permanece en su sitio mientras estallan los demás, así que los dos lados nunca se juntan, y cuando estalla, sus vecinos son los límites fijos del tramo. Eso hace que cada tramo sea un subproblema independiente, que es lo que necesita la programación dinámica.

¿Cuál es la complejidad temporal de Burst Balloons?

La tabla de intervalos tiene aproximadamente n²/2 espacios, y cada uno prueba hasta n globos como el último, así que el tiempo es O(n³) y la memoria O(n²). Para 300 globos, eso equivale a unos 4.5 × 10^6 pasos. Probar todos los órdenes es O(n · n!).

¿Se puede resolver Burst Balloons con un orden voraz?

No. Toda regla sencilla falla en una fila pequeña. Reventar primero el globo más pequeño da 24 en [2, 4, 3], donde se pueden obtener 33. Reventar el globo que paga más en este momento da 42 en [2, 9, 2], donde reventar primero un 2 da 45. Reventar un globo cambia los precios de los posteriores, así que necesitas programación dinámica por intervalos.

¿Por qué agregar un 1 en ambos extremos del arreglo?

Un vecino ausente cuenta como 1, así que dos globos de relleno con valor 1 que nunca estallan proporcionan a cada globo real dos vecinos sin necesidad de casos especiales. También sirven como bordes de todo el problema: la respuesta es el intervalo entre los dos globos de relleno, best[0][m-1].

Python

def maxCoins(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [2, 4, 3]

Esperado

Burst Balloons

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba todos los órdenes de explosión

Recursión en el último globo, con una nota

Rellena la tabla de intervalos por anchura

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares