DP - Sequência de Fibonacci

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.