Burst Balloons

+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, nell’ordine che preferisci. Far scoppiare un palloncino fa guadagnare left × nums[i] × right monete, dove left e right sono i numeri sui suoi vicini attuali: i palloncini più vicini su ciascun lato che sono ancora nella fila. Se manca un vicino, oltre una delle estremità della fila, il suo valore è 1. Dopo uno scoppio, i due vicini diventano adiacenti. Restituisci il massimo numero 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 scoppiare per primo il 4 per ottenere 2 × 4 × 3 = 24 monete. Il 2 e il 3 ora sono vicini, quindi facendo scoppiare il 2 ottieni 1 × 2 × 3 = 6, e il 3, rimasto solo, dà 1 × 3 × 1 = 3. Il totale è 33, e nessun altro ordine dà un risultato migliore: facendo scoppiare per primo il 2 più piccolo, ti fermi già a 24.

+15 test nascosti all’invio

Per approfondire

Puoi anche restituire un ordine esplosivo che frutta il maggior numero di monete?

Suggerimenti

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

0 di 3 aperti

Soluzione

Ogni scoppio cambia chi è accanto a chi, quindi una scelta fatta ora modifica il costo di ogni scoppio successivo. Provare tutti gli ordini significa considerare n! sequenze. Pensare al primo palloncino a scoppiare non divide nemmeno la fila, perché i suoi due lati diventano vicini. Pensare all’ultimo palloncino a scoppiare in un intervallo, invece, sì: resta al suo posto mentre tutti gli altri scoppiano, quindi l’intervallo alla sua sinistra e quello alla sua destra sono indipendenti. Una tabella degli intervalli su questi segmenti risolve il problema in O(n³).

Prova ogni ordine di scoppio

Corretto, ma non termina sui test più grandi

Intuizione

Scegli un qualsiasi palloncino da far scoppiare ora, raccogli left × value × right con i suoi vicini attuali, rimuovilo dalla fila e risolvi la fila più corta allo stesso modo. Fallo per ogni scelta e conserva il totale migliore. Una funzione ricorsiva burstAll(row) fa esattamente questo. Esplora ogni possibile ordine, quindi la risposta è corretta.

È impraticabile per dimensioni reali. Il primo scoppio offre n possibilità, il secondo n-1 e così via: n! ordini. Con 12 palloncini si arriva già a 479,001,600 ordini, e il test più grande ne ha 120. Ricordare i risultati per ogni insieme di palloncini ancora presenti non risolve il problema, perché ci sono 2^n insiemi di questo tipo.

La soluzione è capire perché i sottoproblemi sono così numerosi. Dopo aver fatto scoppiare il palloncino k, quello alla sua sinistra e quello alla sua destra si toccano, quindi ciò che accade a sinistra dipende ancora da ciò che accade a destra. L’approccio successivo sceglie il palloncino su cui concentrarsi in modo che le due parti smettano di influenzarsi a vicenda.

Algoritmo

Scrivi burstAll(row), che restituisce il maggior numero di monete ottenibili dai palloncini in row.
Per ogni posizione k, leggi i vicini, usando 1 oltre ciascuna estremità.
Guadagna left × row[k] × right e aggiungi burstAll della riga senza row[k].
Restituisci il totale migliore tra tutti i valori di k, oppure 0 se la riga è vuota.
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 un memo

Intuizione

Per prima cosa, metti un 1 a entrambe le estremità: vals = [1] + nums + [1]. Questi due non scoppiano mai e rappresentano i vicini mancanti ai bordi. Ora considera un intervallo tra due posizioni left e right che sono ancora intatte, e chiediti: quale palloncino all’interno dell’intervallo scoppia per ultimo?

Supponiamo che sia k. Mentre gli altri palloncini nell’intervallo scoppiano, k è ancora lì, intatto tra loro come un muro. Ogni palloncino tra left e k ha vicini solo in quel tratto, con left e k come confini fissi; lo stesso vale tra k e right. I due tratti sono quindi problemi indipendenti dello stesso tipo. Quando k finalmente scoppia, tutto ciò che si trova tra i confini è sparito, quindi i suoi vicini sono esattamente left e right, e guadagna vals[left] × vals[k] × vals[right]. Scegliere il primo palloncino non produce una suddivisione del genere, perché i suoi due lati diventano vicini.

Questo porta a una ricorsione. solve(left, right) restituisce il massimo numero di monete ottenibile dai palloncini strettamente compresi tra left e right: 0 se l’intervallo è vuoto, altrimenti il valore massimo di solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] per ogni k nell’intervallo. La risposta è solve(0, m-1), l’intervallo tra i due bordi.

Da sola, la ricorsione ricalcola più volte lo stesso intervallo, quindi salva ogni risultato in una tabella memo[left][right] e lo restituisce alle visite successive. Ci sono circa n²/2 intervalli e ognuno prova fino a n palloncini, quindi il lavoro è O(n³). Usa -1 per un intervallo non ancora risolto, perché 0 è una risposta valida. La ricorsione non supera mai n+1 chiamate di profondità, perché ogni chiamata lavora su un intervallo più stretto.

Algoritmo

Costruisci vals come nums con un 1 aggiunto a ciascuna estremità e imposta m alla sua lunghezza.
Crea una matrice 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 i due come ultimo palloncino, conserva il valore più grande di 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 in base alla larghezza

Intuizione

La ricorsione chiede sempre e solo informazioni su intervalli più stretti. Quindi puoi riempire la stessa tabella senza ricorsione, purché riempi gli intervalli stretti prima di quelli ampi. Sia best[left][right] il numero massimo di monete ottenibili dai palloncini strettamente compresi tra left e right, 0 per un intervallo vuoto. Per ogni larghezza a partire da 2, e per ogni intervallo di quella larghezza, prova ogni k al suo interno come ultimo palloncino. best[left][k] e best[k][right] sono intervalli più stretti, quindi i loro valori sono già definitivi.

Prendi [2, 4, 3]. Con i valori aggiunti, è vals = [1, 2, 4, 3, 1] alle posizioni da 0 a 4, e la risposta è best[0][4]. Riempi gli intervalli partendo dai più stretti:

Larghezza 2, un palloncino all'interno: best[0][2] = 1 × 2 × 4 = 8, best[1][3] = 2 × 4 × 3 = 24, best[2][4] = 4 × 3 × 1 = 12.
best[0][3], palloncini 2 e 4: se il 2 è l'ultimo, 0 + 24 + 1 × 2 × 3 = 30; se l'ultimo è il 4, 8 + 0 + 1 × 4 × 3 = 20. Quindi 30.
best[1][4], palloncini 4 e 3: se il 4 è l'ultimo, 0 + 12 + 2 × 4 × 1 = 20; se l'ultimo è il 3, 24 + 0 + 2 × 3 × 1 = 30. Quindi 30.
best[0][4], tutti e tre: se il 2 è l'ultimo, 0 + 30 + 1 × 2 × 1 = 32; se l'ultimo è il 4, 8 + 12 + 1 × 4 × 1 = 24; se l'ultimo è il 3, 30 + 0 + 1 × 3 × 1 = 33. Quindi 33.

Rileggi le scelte vincenti e ottieni l'ordine: il 3 va per ultimo, prima di lui il 2 è l'ultimo dell'intervallo alla sua sinistra, e il 4 va per primo. In totale, 24 + 6 + 3 = 33.

Il lavoro è lo stesso che con la memoizzazione: 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 passaggi per 300 palloncini, e una tabella di 302 × 302 numeri. I semplici cicli evitano milioni di chiamate di funzione, rendendo questa versione diverse volte più veloce della ricorsione in un linguaggio come Python o R.

Algoritmo

Crea vals come nums con un 1 aggiunto a ciascuna estremità e imposta m alla sua lunghezza.
Crea una tabella m × m best riempita di 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 i due.
Imposta best[left][right] al valore massimo di 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

Gli errori più comuni sono un ordine greedy, una ricorsione sulla prima esplosione, un indicatore di memoizzazione errato e una tabella compilata nell’ordine sbagliato.

Gli ordini greedy non funzionano. Far esplodere per prima la pallina più piccola frutta 24 con [2, 4, 3] invece di 33, mentre far esplodere la pallina che paga di più in quel momento frutta 42 con [2, 9, 2], mentre far esplodere per prima una 2 frutta 18 + 18 + 9 = 45.
Dividere in base alla prima esplosione usando i suoi vicini originali, nums[k-1] × nums[k] × nums[k+1] più i due lati, conta vicini che potrebbero essere già scomparsi. Con [2, 4, 3] restituisce 44, più di quanto frutti qualsiasi ordine reale.
Contare i bordi come parte dell’intervallo. left e right sono ancora in piedi quando l’intervallo viene svuotato; esplodono solo le palline strettamente comprese tra loro.
Compilare la tabella riga per riga facendo crescere left. In tal caso best[k][right] per k > left non è ancora stato calcolato e viene letto come 0. Compila la tabella per larghezza oppure procedi con left in ordine decrescente.
Contrassegnare con 0 un intervallo non risolto nella memoizzazione. Un intervallo pieno di palline di valore zero vale davvero 0, quindi sembra non risolto per sempre e viene risolto di nuovo a ogni visita. Usa -1.
Dimenticare i due 1 aggiunti come riempimento, lasciando le palline alle estremità senza vicini con cui moltiplicarsi.
In Lua e R le posizioni riempite vanno da 1 a m, quindi la risposta è best[1][m].

Domande frequenti4

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

Dopo la prima esplosione, i palloncini ai suoi due lati diventano vicini, quindi la parte sinistra e quella destra continuano a influenzarsi a vicenda e non possono essere risolte separatamente. L’ultimo palloncino di un tratto resta al suo posto mentre gli altri esplodono, quindi i due lati non si incontrano mai e, quando esplode, i suoi vicini sono i confini fissi del tratto. Questo rende ogni tratto un sottoproblema indipendente, ciò di cui ha bisogno la programmazione dinamica.

Qual è la complessità temporale di Burst Balloons?

La tabella degli intervalli ha circa n²/2 spazi e ognuno prova fino a n palloncini come ultimo, quindi il tempo è O(n³) e la memoria O(n²). Per 300 palloncini, sono circa 4.5 × 10^6 passaggi. Provare ogni ordine richiede O(n · n!).

Si può risolvere Burst Balloons con un ordine greedy?

No. Ogni regola semplice fallisce su una piccola riga. Far scoppiare per primo il palloncino più piccolo fa guadagnare 24 su [2, 4, 3], dove è possibile ottenere 33. Far scoppiare il palloncino che paga di più in questo momento fa guadagnare 42 su [2, 9, 2], dove far scoppiare per primo un 2 fa guadagnare 45. Far scoppiare un palloncino cambia i prezzi di quelli successivi, quindi ti serve la programmazione dinamica sugli intervalli.

Perché aggiungere un 1 a entrambe le estremità dell’array?

Un vicino mancante vale 1, quindi due palloncini di riempimento con valore 1 che non scoppiano mai danno a ogni palloncino reale due vicini, senza casi speciali. Fungono anche da confini dell'intero problema: la risposta è lo spazio tra i due palloncini di riempimento, best[0][m-1].

Python

def maxCoins(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [2, 4, 3]

Atteso

Burst Balloons

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni ordine di scoppio

Ricorsione sull'ultimo palloncino, con un memo

Completa la tabella degli intervalli in base alla larghezza

Trappole e casi limite

Domande frequenti4

Problemi simili