Programação Dinâmica é uma técnica poderosa utilizada para resolver uma classe particular de problemas como veremos. A ideia é bastante simples, se você solucionou um problema com uma dada entrada, então salve o resultado para referência futura, e também para evitar resolver o mesmo problema novamente.
Sempre se lembre!! “Aqueles que não conseguem lembrar o passado estão condenados a repeti-lo”
Top-Down (De cima para baixo): Comece solucionando o problema quebrando-o em partes. Se você perceber que o problema já foi resolvido, então simplemente pegue a resposta salva. Se ainda não foi resolvido, solucione-o e salve a resposta. Isso é geralmente fácil de pensar e muito intuitivo. É geralmente referenciado como Memorização.
Bottom-Up (De baixo para cima): Analise o problema e veja a ordem em que os subproblemas são resolvidos e comece a solucionar dos problemas mais triviais, até o problema dado. Neste processo, é garantido que os subproblemas são resolvidos antes de resolver o problema. Isto é referenciado como Programação Dinâmica.
O problema da subsequência crescente máxima consiste em encontrar a maior subsequência crescente de uma dada sequência. Dada uma sequência S= {a1 , a2 , a3, a4, … , an-1, an} nós temos que encontrar o maior subconjunto de forma que para todo j e i, j < i no subconjunto aj < ai. Antes de mais nada nós temos que encontrar o valor das maiores subsequências (LSi) para cada índice i com o último elemento da sequência sendo ai. Então a maior LSi será a maior subsequência na sequência dada. Para começar LSi é atribuído a um pois ai é elemento da sequência (último elemento). Então para todo j tal que j < i e aj < ai, nós procuramos o maior LSj e o adicionamos a LSi. Portanto o algoritmo tem complexidade de tempo O(n2). O pseudocódigo para procurar o comprimento da subsequência crescente máxima: A complexidade desse algoritmo poderia ser reduzida utilizando uma estrutura de dados melhor que um array. Armazenando o array antecedente e uma variável como maiorSequenciasAteAgora e seu índice ajudariam a poupar muito tempo. Um conceito similar poderia ser aplicado ao procurar o maior caminho em um grafo acíclico dirigido.
for i=0 to n-1
LS[i]=1
for j=0 to i-1
if (a[i] > a[j] and LS[i]<LS[j])
LS[i] = LS[j]+1
for i=0 to n-1
if (largest < LS[i])
Sugestões ou correções? Abra uma issue no repositório do GitHub, ou faça um pull request você mesmo!
Originalmente contribuído por Akashdeep Goel e atualizado por 3 colaborador(es).