O truque é pensar no último balão a estourar, não no primeiro. Se você escolhe o
primeiro, os vizinhos dos outros mudam e os dois lados ficam acoplados. Se k é o último a estourar
entre l e r, tudo à esquerda e à direita dele já sumiu antes, cada lado sozinho, e na hora de
k os vizinhos são exatamente a[l] e a[r]:
dp[l][r] = max(dp[l][k] + a[l]·a[k]·a[r] + dp[k][r]), com a = [1, ...nums, 1].
Os intervalos são preenchidos do menor para o maior (len).
Sem aba Array: dp[l][r] lê intervalos menores de qualquer linha
(dp[k][r] com vários k), e não só a linha anterior. Não existe uma linha única para reaproveitar,
então a tabela inteira precisa ficar viva.
tempo O(n³)espaço O(n²)n² intervalos (l, r), e para cada um testa até n balões k como o último.
balões · a = [1, ...nums, 1]
l (de pé)
r (de pé)
k (o último)
dentro de (l, r)
tabela dp[l][r]
leitura · dp[l][k] (esquerda de k)
leitura · dp[k][r] (direita de k)
escrita
░░ nunca usado (r ≤ l)
memória · bloco contíguo row-major
m·m células alocadas (m = n + 2), mas só as acima da diagonal são usadas. Espaço O(n²), tempo O(n³):
cada intervalo testa todos os k dentro dele.
Memoization (top-down): f(l, r) devolve o máximo de moedas estourando tudo
entre l e r, com os dois de pé. Para cada k, a pergunta é: "e se
k for o último?" Então f(l, k) e f(k, r) são
independentes, e k rende a[l]·a[k]·a[r]. Os mesmos subintervalos são pedidos por vários pais
(ex.: f(0, 2) por f(0, 3), f(0, 4) e f(0, 5)), daí os cache hits.
Sem aba Array: pelo mesmo motivo da matriz, um intervalo depende de intervalos menores de qualquer
linha, então não há uma linha única para reaproveitar.
tempo O(n³)espaço O(n²)Os mesmos n² estados, cada um com um laço em k. Memo n×n e call stack de até n frames.
balões · a = [1, ...nums, 1]
l (de pé)
r (de pé)
k (o último)
dentro de (l, r)
memo[l][r]
leitura · cache hit
escrita
░░ nunca gravado
memória · heap (memo)
Intervalos vazios (l + 1 = r) não são gravados: o caso base devolve 0 direto. A stack chega a
~n frames (O(n)), e o memo usa O(n²) no heap.