Balões estourados: DP de intervalos reversa

Dadas n balões com valores nums, estourar o balão i rende nums[i-1] * nums[i] * nums[i+1] moedas (o produto dele e de seus vizinhos atuais). Depois que ele estoura, os vizinhos se tornam adjacentes. Encontre o número máximo de moedas que pode ser coletado ao estourar todos os balões. A simulação ingênua é difícil porque estourar um balão altera seus vizinhos — o DP reverso de intervalos contorna essa dificuldade com elegância.

Se tentarmos definir dp[i][j] como o número máximo de moedas obtido ao estourar os balões no intervalo [i, j] e pensarmos em qual balão estourar primeiro, enfrentaremos um problema: estourar primeiro o balão k significa que nums[k-1] e nums[k+1] precisam ser os vizinhos atuais — mas esses balões podem ser estourados depois, alterando os vizinhos dinamicamente. É difícil definir o estado de forma clara na direção direta.

O truque é pensar em qual balão será o último a estourar no intervalo [i, j]. Quando o balão k é o último a estourar em [i, j], todos os outros balões em [i, j] já desapareceram. Portanto, os vizinhos do balão k são exatamente nums[i-1] e nums[j+1] — os balões de limite imediatamente fora do intervalo. Isso torna determinista o cálculo das moedas do último estouro: ele não depende da ordem dos estouros anteriores.

Adicione balões sentinela: acrescente 1 no início e no fim de nums para formar nums = [1] + nums + [1]. Defina dp[i][j] como o número máximo de moedas obtido ao estourar todos os balões estritamente entre os índices i e j (exclusivo), em que nums[i] e nums[j] são os balões de limite que permanecem. Recorrência: para cada candidato a último balão k em (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Preenchemos o vetor com sentinelas, inicializamos a tabela de DP com zero (intervalo vazio = 0 moedas) e a preenchemos em ordem crescente de comprimento dos intervalos. A resposta final é dp[0][n+1], que representa o número máximo de moedas obtido ao estourar todos os balões originais, com as sentinelas como limites permanentes.

Para [3, 1, 5, 8], preenchido com sentinelas para formar [1, 3, 1, 5, 8, 1] (índices 0 a 5). Queremos dp[0][5]. Para intervalos de comprimento 2 (um balão no interior): 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. Construindo progressivamente, a solução ótima é estourar 1 por último entre {3,1,5,8}, depois de estourar primeiro os vizinhos, totalizando 167 moedas.

Há O(n²) intervalos e, para cada intervalo, tentamos O(n) pontos de divisão, resultando em complexidade de tempo O(n³). O espaço é O(n²) para a tabela de DP. Para n = 500 balões, isso corresponde a 125 milhões de operações — viável para as restrições de entrevistas. O preenchimento com sentinelas simplifica o tratamento dos limites: sem ele, seriam necessárias verificações explícitas para saber se i-1 e j+1 estão dentro dos limites.

A mesma solução pode ser escrita de cima para baixo com @lru_cache, o que pode ser mais intuitivo de deduzir durante uma entrevista. Defina solve(i, j) como o número máximo de moedas no intervalo aberto (i, j). A função tenta todos os valores de k como último estouro e memoriza os resultados. As duas abordagens têm complexidades de tempo e espaço idênticas.

Um erro comum é definir dp[i][j] como o número de moedas quando o primeiro balão em [i,j] é estourado, em vez do último. Isso falha porque o cálculo das moedas do primeiro estouro depende dos balões vizinhos que ainda não foram estourados — e o estado desses vizinhos muda à medida que o algoritmo avança. No DP de intervalos, pense sempre no último elemento quando os limites dependem dos elementos restantes.

Escolhem-se sentinelas com valor 1 porque elas atuam como elementos neutros da multiplicação. Quando um balão de limite é o último a estourar, seu valor em moedas é boundary * last * boundary = 1 * last * 1 = last. Usar 0 resultaria em 0 moedas (incorreto), e usar outros valores distorceria o cálculo. O truque das sentinelas unifica todos os casos de limite sem exigir um tratamento especial para os balões mais à esquerda e mais à direita.

No DP de intervalos padrão (multiplicação de cadeias de matrizes), o ponto de divisão k representa o local onde dividimos o problema em dois subproblemas resolvidos independentemente. Nos Balões Explosivos, k é o último balão a estourar no intervalo, tornando os dois subintervalos [i,k] e [k,j] independentes, dado que k ainda está presente como limite. Essa perspectiva invertida é a ideia criativa que torna possível resolver o problema dos Balões Explosivos com DP de intervalos.

Teste sua compreensão dos conceitos de Estruturas de Dados e & Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.

Nesta lição, você aprendeu: a simulação direta falha porque estourar balões altera os vizinhos de forma imprevisível, a ideia inversa define k como o último balão estourado em um intervalo, tornando os vizinhos nums[i] e nums[j], e a recorrência dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) com preenchimento por sentinelas fornece uma solução O(n³). Em seguida, passaremos à DP de mochila, começando pela mochila clássica 0/1 e por sua otimização de espaço.