# 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 - de forma a evitar recálculo - de outros subproblemas que, sobrepostos, compõem o problema original.
O que um problema de otimização deve ter para que a programação dinâmica seja aplicável são duas principais características: subestrutura ótima e superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes.
Problemas de programação dinâmica podem ser abordados de forma top-down ou bottom-up.

## Abordagens Top-Down e Bottom-up
### Top Down

Como os próprios nomes sugerem, a abordagem top-down aborda o problema de forma recursiva 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[ 2 ], F[ 1 ]. 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[ 1 ], depois F[ 2 ], F[ 3 ], e assim por diante até F[ n ]. Observe que, nesta abordagem, na nós 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 tem o mesmo tempo assintótico de execução$^[$.

## Exemplos
### 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)=\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 de forma recursiva 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, tem-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:
Este segundo algoritmo, a princípio, irá ir até à posição 1 e 2 e, então, somar o valor de ambas (1 + 1). Em segunda, o algoritmo recursivo irá adicionar esse valor ao valor da posição 3. Observe que, ao tentar calcular F[3], o algoritmo irá calcular F[1] e F[2], mas F[1] e F[2] já foram calculados, e a primeira linha do pseudocódigo verifica se F[n] já existe e, caso seja verdadeiro, irá apenas retornar seu valor. Com isso, o tempo de execução será Θ(n).

### Exemplo 2: Multiplicação de Cadeia de Matrizes

Imaginemos o processo de multiplicação de $n$ matrizes $M=M_{1}\times M_{2}\times \ldots \times M_{n}$ com dimensões $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\times B\neq B\times A$), mas associativa, o que significa que $A\times (B\times C)=(A\times B)\times C$.
O maior desafio que reside neste problema é, então, otimizar o desempenho do programa que o resolve, ou seja, aproveitar-se da propriedade associativa para encontrar a ordem ótima de se realizar a multiplicação das matrizes, de modo que o número de multiplicações escalares seja mínimo.
Podemos observar que, em geral, multiplicar uma matriz $m\times n$ por uma matriz $n\times p$ exige $m\times n\times p$ operações de multiplicação. As matrizes são multiplicadas aos pares.

#### Problema

Multiplicar $M=M_{1}\times M_{2}\times M_{3}\times M_{4}$ com dimensões $200\times 2$, $2\times 30$, $30\times 20$ e $20\times 5$, respectivamente. Quantas multiplicações são realizadas nessa sequência?
Vamos exemplificar algumas maneiras de realizarmos esta operação:
| Organização dos parênteses | Computação do custo | Custo |
| $M_{1}\times ((M_{2}\times M_{3})\times M_{4})$ | $2\times 30\times 20+2\times 20\times 5+200\times 2\times 5$ | $3.400$ |
| $(M_{1}\times (M_{2}\times M_{3}))\times M_{4}$ | $2\times 30\times 20+200\times 2\times 20+200\times 20\times 5$ | $29.200$ |
| $(M_{1}\times M_{2})\times (M_{3}\times M_{4})$ | $200\times 2\times 30+30\times 20\times 5+200\times 30\times 5$ | $45.000$ |
Como podemos observar, a ordem da multiplicação faz uma grande diferença no tempo de execução final.

#### Solução

Para resolver este problema, tudo que precisamos é saber qual o melhor índice $k$ tal que $M=(M_{1}\times M_{2}\times \ldots \times M_{k})\times (M_{k+1}\times M_{k+2}\times \ldots \times M_{n})$ onde $k$ varia de 1 até (n−1).
Note que esse problema foi decomposto em dois subproblemas. Mais precisamente defina $C(i,j)$ como o número mínimo de multiplicações (ou o custo mínimo) para realizar o produto $M_{i}\times M_{i+1}\times \ldots \times M_{j}$.
Portanto,
    $C(i,j)=min\left\lbrace C(i,k)+C(k+1,j)+m_{i-1}m_{k}m_{j}\right\rbrace$,
onde $k$ varia de i até (j -1), fornece o custo mínimo de multiplicações. Daí, note que:
* $C(i,k)=M_{i}\times M_{i+1}\times \ldots \times M_{k}$ é o número mínimo de operações para realizar de $i$ até $k$;
* $C(k+1,j)=M_{k+1}\times M_{k+2}\times \ldots \times M_{j}$ é o número mínimo de operações para realizar de $(k+1)$ até $j$;
* $m_{i-1}m_{k}m_{j}$ é o número mínimo de operações para realizar esse produto.
Esta expressão constitui uma recorrência típica do método de programação dinâmica. Ela sugere um algoritmo recursivo, mas, uma implementação “bottom up” (de baixo para cima) é mais eficiente. Um algoritmo nesta fórmula tem os seguintes passos iterativos:
* Os $C(i,i)$ são calculados para $1\leq i\leq n$. Claramente, $C(i,i)=0$;
* Os $C(i,i+1)$ são calculados para $1\leq i\leq n-1$;
* Os $C(i,i+2)$ são calculados para $1\leq i\leq n-2$; e assim por diante
Assim, vamos aplicar o algoritmo acima para resolver o exemplo dado anteriormente. Observe que devemos calcular o custo mínimo na ordem crescente da diferença entre $i$ e $j$ . Então, no primeiro passo iterativo, a diferença entre $i$ e $j$ é zero, pois, $i=j$, o que implica:
    $C(1,1)=C(2,2)=C(3,3)=C(4,4)=0$.
No segundo passo, temos i - j = 1, logo,
    $C(1,2)=M_{1}\times M_{2}=12000$
    $C(2,3)=M_{2}\times M_{3}=1200$
    $C(3,4)=M_{3}\times M_{4}=3000$
No terceiro passo, j - i = 2 e com isso, o $k$ varia de 1 a 2. Utilizando a fórmula recursiva:
    $C(1,3)=min(C(1,1)+C(2,3)+m_{0}m_{1}m_{3};$ $C(1,2)+C(3,3)+m_{0}m_{2}m_{3})=min(9200;132000)$
Para $k$ variando de 2 a 3 temos:
    $C(2,4)=min(C(2,2)+C(3,4)+m_{1}m_{2}m_{4};C(2,3)+C(4,4)+m_{1}m_{3}m_{4})=min(3300;1400)$
No último passo, j − i = 3 e com isso, o $k=1,2,3$.
    $C(1,4)=min(C(1,1)+C(2,4)+m_{0}m_{1}m_{4};C(1,2)+C(3,4)+m_{0}m_{2}m_{4};C(1,3)+C(4,4)+m_{0}m_{3}m_{4})=min(3400;45000;29200)$
Por fim, a solução ótima:
    $M=M_{1}\times ((M_{2}\times M_{3})\times M_{4})\to 3.400$ operações.

#### Conclusão

Tentar todas as ordens possíveis de multiplicações para avaliar o produto de $n$ matrizes é um processo ordem exponencial em $n$.
Usando programação dinâmica é possível resolver este problema na ordem polinomial, ou seja $O(n^{3})$ .