Padrões em Programação Dinâmica - 2

Isenção de responsabilidade: o método descrito abaixo não é universal, mas muitas vezes pode resolver um problema ou ajudá-lo a encontrar a solução certa.

Se um problema pede para você destruir/recolher/mesclar (ou similar) um array, então você deve tentar resolvê-lo usando programação dinâmica em subsegmentos.

Vamos obter dp[l][r] - a resposta ideal para um subsegmento com índices de l a r. O recálculo da dinâmica é altamente dependente da tarefa, mas existem as seguintes ideias gerais:

1) Observe os elementos extremos l e r. Se eles corresponderem ou se complementarem de alguma outra forma, provavelmente será possível atualizar o valor de dp[l][r] via dp[l+1][r-1]. Caso contrário via dp[l][r-1] ou dp[l+1[r].

2) Muitas vezes acontece que o segmento [l;r] não pode ser representado por uma única construção. Então é necessário considerar todas as seções possíveis deste subsegmento em duas partes, ou seja, iterar sobre o elemento k de l a r-1 e recalcular dp[l][r] através de dp[l][k] e dp[ k+1][r] . Em subsegmentos menores, essas seções também foram classificadas, portanto, de fato, as opções para dividir o subsegmento [l;r] não apenas em duas partes, mas em qualquer número delas são levadas em consideração.
 

Isenção de responsabilidade: o método descrito abaixo não é universal, mas muitas vezes pode resolver um problema ou ajudá-lo a encontrar a solução certa.

Se você precisa verificar a existência de uma permutação em um problema, ou encontrar o número de permutações que correspondem, ou algo similar, então você deve considerar o uso da programação dinâmica de subconjuntos.

O parâmetro principal será uma máscara de bits, que mostrará quais elementos já foram incluídos na permutação e quais não foram. Muitas vezes também é necessário um segundo parâmetro que indica qual elemento foi incluído por último.

Freqüentemente, as permutações podem ser vistas no contexto de caminhos em gráficos. Assim, consideremos um exemplo clássico - o problema do caminho hamiltoniano.
Um caminho hamiltoniano é um caminho simples que passa por cada vértice do grafo exatamente uma vez. Pode ser representado simplesmente como uma permutação de comprimento n, onde n é o número de vértices. A ordem dentro desta permutação indicará a ordem na qual os vértices neste caminho são percorridos.

Para verificar a presença de um caminho hamiltoniano no grafo, vamos iniciar a dinâmica dp[mask][last] - existe um caminho simples que contornou os vértices marcados com uns no bitmask da máscara e acabou no último vértice.
Os valores iniciais serão dp[2ⁱ][i] = verdadeiro, o resto falso, o que significa que sempre há um caminho vazio começando em qualquer um dos vértices.
Tendo o valor true em dp[mask][last] faremos as transições para frente, no sentido de "estender o caminho". Ou seja, procuraremos o número de vértices marcados com zero na máscara (ainda não os visitamos no caminho) e ao mesmo tempo de forma que haja uma aresta do último a este vértice (o caminho deve ser estendido por uma aresta existente). Ou seja, fazemos dp[mask | 2^k][k] = true if dp[mask][last] = true AND mask & 2^k = 0 (o vértice k ainda não foi visitado) E há uma última aresta -> k.
Por fim, existe um caminho hamiltoniano se houver um valor verdadeiro em dp para os parâmetros da bitmask de todos os uns e qualquer último vértice.