Programação dinâmica
Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória. Ela é aplicável a problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada — para evitar recálculo — de outros subproblemas que, sobrepostos, compõem o problema original.
Imagem: arlifrancis · CC0 · Openverse
Top Down
Como os próprios nomes sugerem, a abordagem top-down aborda o problema recursivamente comum, ou seja, no exemplo do algoritmo de Fibonacci (mais abaixo), começamos pelo n-ésimo número e em, recursivamente, ir calculando os valores de F[ n-1 ], F[ n-2 ], F[ n-3 ],..., F, F. Nesta abordagem, os valores são armazenados em uma tabela e, para a i-ésima iteração, verifica-se se F[ i ] já foi calculado.
Bottom Up
Na abordagem bottom-up, vamos calculando os subproblemas menores e aumentando a complexidade com o passar do tempo, ou seja, para o exemplo de Fibonacci, começaríamos calculando F, depois F, F, e assim por diante até F[ n ]. Observe que, nesta abordagem, sabemos que, na i-ésima iteração, F[ i-1 ] já foi resolvido, logo não precisamos verificar toda vez como na top-down. Ao consultar o exemplo 1, do Algoritmo de Fibonacci, isso deve ficar mais claro. Em geral, ambas as abordagens têm o mesmo tempo assintótico de execução[carece de fontes?].
Imagem: arlifrancis · CC0 · Openverse
Exemplo 1: Sequência de Fibonacci
Como exemplo simples de programação dinâmica, com alguma frequência, alguns textos, utilizam a determinação recursiva da Sequência de Fibonacci. F ( n ) = { 1 se n ≤ 1 F ( n − 1 ) + F ( n − 2 ) caso contrário } {\displaystyle F(n)=\left\lbrace {\begin{matrix}1&{\text{se }}n\leq 1\\F(n-1)+F(n-2)&{\text{caso contrário}}\end{matrix}}\right\rbrace } Quando implementada recursivamente sem maiores cuidados e sem memorização, a dupla chamada a F na segunda linha causa a necessidade da repetição de cálculos, que faz com que o tempo cresça exponencialmente. Para implementar em PD, têm-se os seguintes pseudocódigos: Esse primeiro irá inicializar as posições 1 e 2 com o valor 1 e o resto com “-1”. Esse primeiro algoritmo somente cria e inicializa o vetor, e ao final chama o algoritmo que de fato irá calcular os valores de Fibonacci:
Exemplo 2: Multiplicação de Cadeia de Matrizes
Imaginemos o processo de multiplicação de n {\displaystyle n} matrizes M = M 1 × M 2 × … × M n {\displaystyle M=M_{1}\times M_{2}\times \ldots \times M_{n}} com dimensões m 0 × m 1 , m 1 × m 2 , … , m n − 1 × m n {\displaystyle m_{0}\times m_{1},m_{1}\times m_{2},\dotsc ,m_{n-1}\times m_{n}} , respectivamente. O problema em essência é trivial, pois se multiplicarmos sequencialmente as matrizes obteremos facilmente o resultado esperado. É interessante lembrar que a multiplicação de matrizes não é comutativa (em geral, A × B ≠ B × A {\displaystyle A\times B\neq B\times A} ), mas associativa, o que significa que A × ( B × C ) = ( A × B ) × C {\displaystyle A\times (B\times C)=(A\times B)\times C} .
