Burst Balloons: DP sugli intervalli al contrario

Data una serie di n palloncini con valori nums, far scoppiare il palloncino i produce nums[i-1] * nums[i] * nums[i+1] monete (il prodotto del palloncino stesso e dei suoi vicini attuali). Dopo lo scoppio, i vicini diventano adiacenti. L'obiettivo è trovare il numero massimo di monete ottenibile facendo scoppiare tutti i palloncini. La simulazione ingenua è difficile perché far scoppiare un palloncino modifica i vicini: la DP inversa su intervalli evita elegantemente questa difficoltà.

Se si definisse dp[i][j] come il numero massimo di monete ottenibile facendo scoppiare i palloncini nell'intervallo [i, j] e si considerasse quale palloncino far scoppiare per primo, sorgerebbe un problema: far scoppiare per primo il palloncino k significa che nums[k-1] e nums[k+1] devono essere i vicini attuali, ma questi palloncini potrebbero essere fatti scoppiare in seguito, modificando dinamicamente i vicini. È difficile definire lo stato in modo chiaro procedendo in avanti.

Il trucco consiste nel ragionare su quale palloncino viene fatto scoppiare per ultimo nell'intervallo [i, j]. Quando il palloncino k è l'ultimo a scoppiare in [i, j], tutti gli altri palloncini in [i, j] sono già scomparsi. I vicini del palloncino k sono quindi esattamente nums[i-1] e nums[j+1], cioè i palloncini di confine appena fuori dall'intervallo. Questo rende deterministico il calcolo delle monete dell'ultimo scoppio: non dipende dall'ordine degli scoppi precedenti.

Si aggiungano i palloncini sentinella: si anteponga e si aggiunga 1 a nums per ottenere nums = [1] + nums + [1]. Si definisca dp[i][j] come il numero massimo di monete ottenibile facendo scoppiare tutti i palloncini strettamente compresi tra gli indici i e j (estremi esclusi), dove nums[i] e nums[j] sono i palloncini di confine che rimangono. Ricorrenza: per ogni possibile ultimo palloncino k in (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Si estende l'array con le sentinelle, si inizializza la tabella DP a zero (un intervallo vuoto vale 0 monete) e si procede per lunghezze crescenti degli intervalli. La risposta finale è dp[0][n+1], che rappresenta il numero massimo di monete ottenibile facendo scoppiare tutti i palloncini originali, con le sentinelle come confini permanenti.

Per [3, 1, 5, 8], completato con le sentinelle diventa [1, 3, 1, 5, 8, 1] (indici 0-5). Si vuole calcolare dp[0][5]. Per gli intervalli length=2 (un palloncino all'interno): 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. Procedendo, la soluzione ottimale consiste nel far scoppiare 1 per ultimo tra {3,1,5,8}, dopo aver fatto scoppiare prima i vicini, ottenendo un totale di 167 monete.

Ci sono O(n²) intervalli e per ciascun intervallo si provano O(n) punti di divisione, ottenendo una complessità temporale O(n³). Lo spazio richiesto dalla tabella DP è O(n²). Per n = 500 palloncini si tratta di 125 milioni di operazioni, un numero gestibile con i vincoli tipici dei colloqui. L'aggiunta delle sentinelle semplifica la gestione dei bordi: senza di esse, sarebbe necessario verificare esplicitamente se i-1 e j+1 rientrano nei limiti.

La stessa soluzione può essere scritta con un approccio top-down usando @lru_cache, che potrebbe risultare più intuitivo da ricavare durante un colloquio. Si definisca solve(i, j) come il numero massimo di monete nell'intervallo aperto (i, j). La funzione prova ogni k come ultimo palloncino da far scoppiare e memorizza i risultati. Entrambi gli approcci hanno la stessa complessità temporale e spaziale.

Un errore comune consiste nel definire dp[i][j] come il numero di monete ottenibile quando il primo palloncino in [i,j] viene fatto scoppiare, invece dell'ultimo. Questo non funziona perché il calcolo delle monete per il primo scoppio dipende dai palloncini vicini che non sono ancora stati fatti scoppiare, e lo stato di questi vicini cambia man mano che l'algoritmo procede. Nella DP su intervalli, quando i confini dipendono dagli elementi rimanenti, bisogna sempre ragionare sull'ultimo elemento dell'intervallo.

Si scelgono sentinelle di valore 1 perché agiscono da elementi neutri per la moltiplicazione. Quando un palloncino di confine è l'ultimo a scoppiare, il suo valore in monete è boundary * last * boundary = 1 * last * 1 = last. Usare 0 produrrebbe 0 monete (sbagliato), mentre usare altri valori altererebbe il calcolo. Il trucco delle sentinelle unifica in modo pulito tutti i casi ai bordi senza dover gestire separatamente il palloncino più a sinistra e quello più a destra.

Nella DP su intervalli standard (moltiplicazione a catena di matrici), il punto di divisione k indica dove dividere il problema in due sottoproblemi risolti indipendentemente. In Burst Balloons, k è l'elemento che viene fatto scoppiare per ultimo nell'intervallo, rendendo indipendenti i due sottointervalli [i,k] e [k,j], dato che k è ancora presente come elemento di confine. Questa prospettiva inversa è l'idea creativa che rende risolvibile Burst Balloons con la DP su intervalli.

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato: la simulazione in avanti fallisce perché l'esplosione dei palloncini modifica i vicini in modo imprevedibile, l'intuizione inversa definisce k come l'ultimo palloncino fatto esplodere in un intervallo, rendendo nums[i] e nums[j] i vicini e la ricorrenza dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) con il padding tramite sentinelle fornisce una soluzione O(n³). Ora passeremo alla DP dello zaino, iniziando dal classico zaino 0/1 e dalla sua ottimizzazione dello spazio.