DP - Problema das k curvas

Este problema consiste em  contar o número de caminhos para chegar iniciando até parte inferior direita em uma matriz MxN realizando no máximo k curvas como mostrado na figura.

O que é uma curva?
Cada movimento que altera a direção é considerado uma curva, isto é,

• se nós estávamos nos movendo ao longo da linha e passamos a nos mover ao longo da coluna
• ou se estávamos nos movendo ao longo da coluna e agora passamos a mover ao longo da linha.

Podemos resolver este problema em tempo polinomial, utilizando uma matriz multidimensional com 4 dimensões para guardar a quantidade de caminho nas células considerando a quantidade de curvas e mudanças de direção.

O vídeo mostra como implementar a solução deste problema.

DP - Problema de mochila

O problema da mochila é um problema de otimização combinatória. Isto que dizer que temos que trabalhar com diversas combinações e obter uma combinação que é ótima, ou seja, é a melhor segundo algum critério. O problema da mochila é um dos 21 problemas NP-completos de Richard Karp.

Este tipo de problema queremos preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é preencher a mochila com o maior valor possível, contudo não podemos ultrapassar o peso máximo. Vemos portanto que formulação do problema é extremamente simples, porém sua solução é mais complexa.

No vídeo apresentamos como resolver esta versão da mochila.

Existem diversas variações do problema da mochila. Se você estiver curioso dê uma olhada na wikipedia.

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.