Burst Balloons

Q: Qual è la complessità temporale di Burst Balloons?

Tempo O(n³) e memoria O(n²) : circa n²/2 intervalli, ognuno dei quali prova fino a n palloncini come ultimo. Per 300 palloncini sono circa 4.5 × 10^6 passaggi. Provare ogni ordine richiede O(n · n!) .

DifficileProgrammazione dinamica

+10

Ti viene data una fila di palloncini rappresentata da nums, dove nums[i] è il numero sul palloncino i. Li fai scoppiare tutti, uno alla volta, in qualsiasi ordine. Far scoppiare un palloncino ti fa guadagnare left × nums[i] × right monete, dove left e right sono i numeri sui suoi vicini attuali, i palloncini più vicini ancora presenti nella fila, uno per ciascun lato. Un vicino mancante vale 1. Dopo uno scoppio, i suoi due vicini diventano adiacenti. Restituisci il numero massimo di monete che puoi raccogliere.

Funzione

maxCoins(nums: integer-array) → integer

numsinteger-array: i numeri sui palloncini, da sinistra a destra
Restituisceinteger: il maggior numero di monete che puoi raccogliere facendo scoppiare ogni palloncino

Vincoli

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
La risposta è inferiore a 3 × 10⁸, quindi rientra in un intero con segno a 32 bit.

Esempi

Input: nums = [2, 4, 3]
Output: 33
Spiegazione: Fai esplodere il 4 per 2 × 4 × 3 = 24. Il 2, ora accanto al 3, vale 1 × 2 × 3 = 6, e il 3 vale 3: 33 in tutto.

Per approfondire

Puoi anche restituire un ordine esplosivo che faccia guadagnare più monete?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni scoppio cambia chi si trova accanto a chi, quindi il primo palloncino che fai scoppiare non divide la fila: i suoi due lati diventano vicini. Lo fa l’ultimo palloncino a scoppiare in un tratto. Rimane mentre tutto il resto scompare, quindi i tratti ai suoi due lati sono indipendenti e una tabella degli intervalli sui tratti risolve il problema in O(n³).

Prova ogni ordine di scoppio

Corretto, ma non termina sui test più grandi

Intuizione

Scegli un palloncino, raccogli left × value × right, rimuovilo e risolvi la riga più corta allo stesso modo, mantenendo il totale migliore tra tutte le scelte. Prova ogni ordine, quindi è corretta.

La prima rimozione offre n possibilità, la successiva n-1 e così via: n! ordini, già 479,001,600 per 12 palloncini. Memorizzare i risultati per ogni insieme di palloncini rimasti non aiuta, perché ci sono 2^n insiemi.

Algoritmo

Scrivi burstAll(row), il numero massimo di monete ottenibile dai palloncini in row, 0 per una riga vuota.
Per ogni posizione k, guadagna left × row[k] × right, usando 1 oltre ciascuna delle due estremità, più burstAll della riga senza row[k].
Restituisci il totale migliore tra tutti i k e chiama 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)

Ricorsione sull'ultimo palloncino, con una memo

Intuizione

Aggiungi un 1 a ciascuna estremità della riga: vals = [1] + nums + [1]. I valori aggiunti non scoppiano e prendono il posto dei vicini mancanti. Sia solve(left, right) il numero massimo di monete ottenibile dai palloncini strettamente compresi tra due posizioni occupate.

Supponiamo che k sia l’ultimo a scoppiare in quell’intervallo. Tutti gli altri palloncini al suo interno scoppiano mentre k resta in piedi come un muro, quindi la parte tra left e k vede solo i propri palloncini e due bordi fissi, e lo stesso vale per la parte tra k e right. Quando k scoppia, i suoi vicini sono esattamente left e right. Quindi, per ogni k, il risultato migliore per l’intervallo è il migliore delle due parti più vals[left] × vals[k] × vals[right]. La risposta è il risultato per l’intervallo tra i due valori aggiunti. Ci sono circa n²/2 intervalli, ognuno dei quali prova fino a n palloncini, quindi la memoizzazione porta la complessità a O(n³).

Algoritmo

Costruisci vals come nums con un 1 aggiunto a ciascuna estremità e imposta m alla sua lunghezza.
Crea una tabella m × m inizializzata con -1.
Scrivi solve(left, right): restituisci 0 se right - left < 2 e il valore memorizzato, se presente.
Altrimenti, prova ogni k strettamente compreso tra loro come ultimo palloncino, conserva il valore più grande tra solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] e memorizzalo.
Restituisci 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 tabella degli intervalli per larghezza

Intuizione

La ricorsione considera solo intervalli più ristretti, quindi riempi la stessa tabella con dei cicli, dagli intervalli più ristretti a quelli più ampi. Così best[left][k] e best[k][right] sono definitivi ogni volta che servono per un intervallo più ampio.

Per [2, 4, 3], completato con [1, 2, 4, 3, 1], best[0][4] prova ogni palloncino come ultimo. Se il 3 è l’ultimo, si ottiene best[0][3] = 30 più 1 × 3 × 1, per un totale di 33, il migliore dei tre.

Il lavoro è equivalente a quello della versione con memoizzazione, ma i semplici cicli evitano milioni di chiamate di funzione, rendendo questa versione diverse volte più veloce in un linguaggio come Python o R.

Algoritmo

Crea vals come nums aggiungendo un 1 a ciascuna estremità, e imposta m alla sua lunghezza.
Crea una tabella m × m best inizializzata con 0.
Per ogni larghezza da 2 a m-1 e per ogni left con right = left + width all'interno dell'array, prova ogni k strettamente compreso tra loro.
Imposta best[left][right] al massimo tra best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right].
Restituisci 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]

Trappole e casi limite

Dividere considerando lo scoppio del primo palloncino insieme ai suoi vicini originali, nums[k-1] × nums[k] × nums[k+1], più i due lati. Quei vicini potrebbero essere già spariti: con [2, 4, 3] restituisce 44, più di quanto si ottenga con qualsiasi ordine reale.
Riempire la riga della tabella procedendo dall’alto verso il basso, facendo crescere left. Quindi best[k][right] per k > left non è ancora stato calcolato e viene letto come 0. Riempi la tabella in base alla larghezza oppure procedi con left in ordine decrescente.
Contrassegnare con 0 un intervallo non risolto nella memoizzazione. Un intervallo di palloncini con valore zero vale davvero 0, quindi viene risolto di nuovo a ogni visita. Usa -1.
In Lua e R le posizioni aggiunte vanno da 1 a m, quindi la risposta è best[1][m].

Domande frequenti3

Perché Burst Balloons sceglie l’ultimo palloncino invece del primo?

Dopo la prima esplosione, i suoi due lati diventano vicini, quindi continuano a influenzarsi a vicenda. L’ultimo palloncino di un segmento rimane in piedi mentre gli altri esplodono, quindi i suoi due lati non si incontrano mai e ciascuno costituisce un sottoproblema indipendente. Quando esplode, i suoi vicini sono i confini del segmento.

Qual è la complessità temporale di Burst Balloons?

Tempo O(n³) e memoria O(n²): circa n²/2 intervalli, ognuno dei quali prova fino a n palloncini come ultimo. Per 300 palloncini sono circa 4.5 × 10^6 passaggi. Provare ogni ordine richiede O(n · n!).

È possibile risolvere Scoppia i palloncini con un ordine greedy?

No. Far scoppiare per primo il palloncino più piccolo fa guadagnare 24 con [2, 4, 3], dove è possibile ottenere 33. Far scoppiare quello che dà di più in quel momento fa guadagnare 42 con [2, 9, 2], mentre far scoppiare per primo un 2 fa guadagnare 18 + 18 + 9 = 45. Ogni scoppio cambia i prezzi di quelli successivi.

def maxCoins(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

nums = [2, 4, 3]

Output atteso

Burst Balloons

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni ordine di scoppio

Ricorsione sull'ultimo palloncino, con una memo

Completa la tabella degli intervalli per larghezza

Trappole e casi limite

Domande frequenti3

Problemi simili