Padrão de DP de intervalos e ordem de preenchimento

Programação dinâmica por intervalos é um padrão de programação dinâmica em que o estado dp[i][j] representa a resposta ideal para o subproblema que abrange os índices i até j. A ideia principal é resolver primeiro os intervalos menores e expandir a solução até o intervalo completo. Esse padrão modela naturalmente problemas como multiplicação de cadeias de matrizes, particionamento de palíndromos e estouro de balões, nos quais os limites do subproblema são as extremidades esquerda e direita de um intervalo.

Na programação dinâmica por intervalos, o estado é dp[i][j], em que i <= j. Os casos-base são intervalos de um único elemento: dp[i][i]. Eles são resolvidos trivialmente — por exemplo, uma única matriz tem custo de multiplicação zero. Os intervalos de dois elementos, dp[i][i+1], também costumam ter respostas simples. Preenchemos a tabela para comprimentos crescentes de intervalo, começando pelo comprimento 1 e indo até n.

O detalhe fundamental na programação dinâmica por intervalos é a ordem de preenchimento. Devemos calcular todos os intervalos de comprimento L antes de calcular os intervalos de comprimento L+1, porque um intervalo maior depende de subintervalos menores. O laço externo percorre o comprimento do intervalo de 2 até n, o laço intermediário define o limite esquerdo i, e derivamos o limite direito como j = i + L - 1.

O problema clássico de programação dinâmica por intervalos é a multiplicação de cadeias de matrizes: dadas matrizes com dimensões dims[0..n], encontre o número mínimo de multiplicações escalares necessárias para calcular o produto. Multiplicar a matriz A(p×q) pela matriz B(q×r) custa p*q*r operações. dp[i][j] = custo mínimo para multiplicar as matrizes i até j. O ponto de divisão k determina onde a sequência é dividida em duas subcadeias.

Vamos acompanhar o exemplo de cadeia de matrizes com as dimensões [10, 30, 5, 60], que representa três matrizes: A(10×30), B(30×5), C(5×60). Para dp[0][2], tentamos a divisão em k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000; e em k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Portanto, dp[0][2] = 4500, obtido ao multiplicar AB primeiro.

Ao calcular dp[i][j], consultamos dp[i][k] e dp[k+1][j] para todo k em [i, j-1]. Ambos os subintervalos têm comprimento estritamente menor que [i, j]. Ao percorrer os comprimentos do menor para o maior, todos os subintervalos necessários são calculados antes de precisarmos deles. Esse é o argumento fundamental de correção da ordem de preenchimento da programação dinâmica por intervalos — os intervalos menores são sempre dependências dos maiores.

Como alternativa, a programação dinâmica por intervalos pode ser implementada de cima para baixo com memorização. Escrevemos uma função recursiva solve(i, j) que retorna o custo ideal para o intervalo [i, j] e armazenamos os resultados em um dicionário. A ordem de preenchimento é tratada automaticamente pela recursão. A abordagem de cima para baixo costuma ser mais fácil de compreender, mas pode ter sobrecarga de chamadas de função; a abordagem de baixo para cima é mais rápida na prática para entradas grandes.

A programação dinâmica por intervalos tem O(n²) estados (todos os pares (i, j)), e cada estado percorre O(n) pontos de divisão, resultando em tempo O(n³) no total. O espaço é O(n²) para a tabela de programação dinâmica. Para a multiplicação de cadeias com 100 matrizes, isso corresponde a 1.000.000 de operações — totalmente viável. Esse padrão aparece em muitos problemas difíceis do LeetCode e é um dos favoritos em entrevistas da FAANG devido à sua estrutura pouco óbvia.

Para reconstruir o parentesamento real (e não apenas o custo), armazene uma tabela split[i][j] separada, registrando qual k atingiu o mínimo em cada estado. Em seguida, leia as divisões recursivamente: reconstruct(i, j) exibe o agrupamento ideal ao fazer a recursão sobre [i, split[i][j]] e [split[i][j]+1, j]. Essa técnica se aplica a todos os problemas de programação dinâmica por intervalos.

O modelo universal de programação dinâmica por intervalos tem três partes: (1) inicializar os casos-base para elementos únicos; (2) percorrer comprimentos crescentes e, para cada comprimento, percorrer os limites esquerdos válidos, calculando o limite direito; e (3) para cada intervalo, percorrer todos os pontos de divisão e aplicar a recorrência específica do problema. A única coisa que muda entre os problemas é a fórmula da recorrência dentro do laço mais interno.

Os problemas que usam programação dinâmica por intervalos incluem: Multiplicação de Cadeias de Matrizes (minimizar operações), Estouro de Balões (maximizar moedas), Impressora Estranha (minimizar operações de impressão), Triangulação de Polígono com Pontuação Mínima e Particionamento de Palíndromos II. Todos usam o mesmo esqueleto de ordem de preenchimento, mas recorrências diferentes. Reconheça o padrão quando um problema pedir um valor ideal sobre um intervalo ou sequência que possa ser dividida em qualquer ponto interno.

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

Nesta lição, você aprendeu que: a programação dinâmica por intervalos usa dp[i][j] para representar a resposta ideal sobre um intervalo; a ordem de preenchimento deve seguir o comprimento crescente dos intervalos, para que os subintervalos sejam calculados primeiro; e o modelo universal tem tempo O(n³) e espaço O(n²). Em seguida, exploraremos a maior subsequência e a maior substring palindrômicas usando esse mesmo padrão.