A sequência de Fibonacci é uma sucessão de números que, misteriosamente, aparece em muitos fenômenos da natureza. Ela foi descrita no final do século 12 pelo italiano Leonardo Fibonacci. É uma sequência infinita que começa com 0 e 1 ou 1 e 1 (depende de onde você está lendo a informação). Os números seguintes são sempre a soma dos dois números anteriores. Portanto, depois de 0 e 1, vêm 1, 2, 3, 5, 8, 13, 21, 34…
Logo
F[1] = 1
F[2] = 1
F[n] = F[n-1] + F[n-2], para n > 3
Esta definição mostra claramente como podemos implementar a sequência usando recursividade, isto é, podemos criar uma função e chamá-la recursivamente para obter os valores F[n-1] e F[n-2] até chegar nos casos base que são F[1] e F[2].
Contudo podemos ver na figura abaixo que existe muito trabalho repetido. Podemos usar os recursos da programação dinâmica para melhorar o desempenho deste cálculo.
No vídeo vemos como implementar a sequência de Fibonacci usando recursividade e usando programação dinâmica.
Dado um valor de troco N (um número inteiro no nosso exemplo). Nós temos suprimento infinito de cada tipo de moeda do conjunto S = {S1, S2, .., SM}. Note que temos portanto M tipos de moedas e teoricamente temos infinitas delas. Quantas maneiras podemos combinar as moedas para obter um troco exato? A ordem das moedas não importa.
Por exemplo temos que dar um troco de N = 4 dinheiros.
O conjunto de moedas que temos é S = {1,2,3}.
Podemos ver que existem quatro soluções: {1,1,1,1}, {1,1,2}, {2,2}, {1, 3}.
Assim a resposta do programa deve ser 4.
Este problema pode ser resolvido por DP. Identificamos as duas características:
1) Subestrutura ótima
Para contar soluções, podemos dividir todas as soluções em dois subconjuntos:
a) Todas as soluções que não contêm moeda "i" (ou seja Si).
b) As soluções que contêm pelo menos uma moeda Si.
Desta forma podemos escrever o problema de contagem como
C(S, n) = C(S', n) + C(S, N-Si)
Onde S' = S - {Si}
Desta forma vemos que o problema tem a propriedade subestrutura ótima como o problema pode ser resolvido usando soluções de subproblemas. A equação e as condições abaixa deixam claro também que os problemas são sobrepostos.
Temos que notar que existem algumas condições:
a) C(S,0) = 1, pois se n=0 existe uma solução que não precisa de mais moedas
b) C(S,n) = 0, se n<0, pois n negativo, não há uma solução do problema (subtraiu demais)
c) C(S,n) = 0, se S = {} e n > 0, pois se não temos moedas para dar um troco "n" (já que n é maior que zero), não tem como acharmos uma solução.
O que falta no exemplo acima? Se você falou a memorização dos dados... acertou!
A memorização aumenta bastante a velocidade, uma vez que não precisamos recalcular.
Em computação a programação dinâmica é um método utilizado para a construção de algoritmos capazes de resolver problemas computacionais. Este método é aplicável aos problemas cuja solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada.
A solução anterior é memorizada para evitar recálculo.
Desta forma a programação dinâmica ou DP (Dynamic Programming) resolve um problema a partir de subproblemas que sobrepostos compõem o problema original.
Um problema computacional pode ser resolvido por DP se possuir duas características denominadas (1) subestrutura ótima e (2) superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução para o problema contém em seu interior soluções para subproblemas - isto é temos a mesma fórmula de recorrência. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes - é aí que entra a memorização.
A DP não é uma forma intuitiva de pensar, portanto temos que ver diversos exemplos para conseguir compreender e assimilar como ela trabalha. Vou criar a partir de agora um conjunto de posts que mostram como solucionar alguns problemas usado DP. Estes posts virão com uma implementação completa em Java para o problema. O primeiro da série busca descobrir de quantas maneiras é possível dar um troco (N) utilizando um determinado conjunto de moedas.
