Técnicas de Programação 03 - Programação Dinâmica

Aula de Rogério Júnior

Na aula de funções vimos como calcular o n-ésimo número da sequência de Fibonacci. Foi mostrada, também, a árvore de recursão de calcular o 5º número da sequência de Fibonacci, que mostra todas as chamadas que temos que fazer dessa função. Reveja: Note que o Fib(2), por exemplo, é recalculado 3 vezes na árvore, o que gera o recálculo, para cada chamada do Fib(2) de dois outros valores: Fib(0) e Fib(1). Percebe como sempre chamar a recursão é ineficiente? O número de chamadas em uma função que calcula o Fibonacci cresce exponencialmente e, se formos calcular o Fib de números maiores que 60, já levamos TLE na maioria dos corretores. Imagine uma chamada de Fib que teria que recalcular o valor de Fib(5): ele teria que chamar, novamente, todas os 14 valores de Fib mostrados na árvore acima, mas, e se salvarmos o valor de Fib(5) em algum lugar, depois que o calcularmos? Assim, da próxima vez que precisássemos do valor de Fib(5), teríamos ele guardado sem termo que chamar nenhuma outra função, acessando-o em O(1)! Bastava que guardássemos uma variável com o valor de Fib(5), começando com 0, por exemplo e, quando fôssemos chamar a função, iríamos verificar se o valor lá salvo ainda é zero. Se fosse, então ainda não calculamos esse valor, mas assim que terminássemos, iríamos trocar o valor de da variável de 0 para o valor de Fib(5), fazendo com que das próximas vezes, bastasse retornar o valor lá salvo. Mas por quê fazer isso só com 5?

A ideia de Programação Dinâmica (ou Dynamic Programming (DP), em inglês) é evitar o recálculo de uma função para os mesmos parâmetros que já calculamos alguma vez, salvando todos os resultados que já obtemos até então, calculando o valor da função apenas se ele nunca foi calculado. Assim, só calculamos cada valor da função uma única vez! Chamamos de estado da DP um conjunto de parâmetros que define a situação que ela precisa calcular, e se ela passar pelo mesmo estado duas vezes, ela só precisa calcular seu valor uma vez e guardá-lo para o futuro, se ela precisar. No caso, os possíveis estados da DP são as possíveis posições da sequência que ela quer calcular.

Vamos tentar refazer a função que calcula o n-ésimo termo da sequência de Fibonacci de maneira mais eficiente. Para tal, vamos criar um vetor auxiliar int dp[MAXN], onde MAXN é a maior posição da sequência que posso querer calcular. Ele começará com todos os valores iguais a -1 (pois sei que nenhum termo da sequência em posição positiva tem esse valor). Assim, se o valor de dp[i] for -1, então ainda não calculei esse valor. Agora basta refazer a função fib fazendo-a verificar, primeiramente, se já tenho salvo, em dp[x] ("if(dp[x]!=-1)"), o valor de fib(x), retornando-o se isso ocorrer. Caso eu ainda não tenha calculado esse valor, faço a função recursiva e lembro de salvar o valor calculado em dp[x] antes de retornar a função! Uma pequena observação é que existe uma função da cstring chamada memset que faz todos as posições de um array receberem algum valor escolhido. Ela tem três parâmetros e a seguinte gramática ("memset(nome_do_vetor, valor, sizeof(nome_do_vetor));"). Ela troca todos os bytes do vetor pelo valor escolhido e, como um int tem 4 bytes, não podemos usá-la em todos os casos. Saiba que ela funciona para 0 e -1, o que felizmente é o nosso caso. Segue o código para melhor entendimento:

Observe que, com essa função, evito vária chamadas recursivas, o que otimiza muito a complexidade, pois agora só calculo cada valor da sequência uma única vez, logo, a complexidade fica O(n), onde n é a posição da sequência que queremos calcular. Para você entender isso melhor, veja como fica a nova árvore de recursão dessa versão mais eficiente da função Fib, que só calcula os valores 1 vez e para a recursão sempre que houver recálculo: Em qualquer função recursiva, podemos [e devemos] guardar o valores já calculados e evitar recálculo com programação dinâmica. A função fib tem um único parâmetro, por isso podia guardar seu valores em um vetor. Se precisássemos usar uma função de nome dp que recebe dois inteiros como parâmetros, do tipo "int dp(int parametro1, int parametro2){}" iríamos guardar seus valores em uma matriz nxm ("int tab[n][m];"), onde n é o maior valor possível de parametro1 e m o maior valor possível de parametro2. Desse modo, iríamos guardar o valor de dp(x, y) em tab[x][y]. Façamos agora algumas observações: As duas últimas linhas da função apresentada apresentada: "dp[x]=fib(x-1)+fib(x-2);" e "return dp[x];" podem ser substituídas por um único comando: "return dp[x]=fib(x-1)+fib(x-2);", que executa exatamente os dois comando anteriores nessa mesma ordem. Usaremos sempre isso em programação dinâmica.

Tipos de Abordagem

Note que usamos uma função recursiva que chama os casos mais de cima (mais distantes dos casos base) da DP (como chamamos a função usa programação dinâmica), até chegar aos casos base e só então ir voltando a recursão. Esse tipo de abordagem, em que usamos uma função recursiva no método de dividir para conquistar para calcular os valores da DP é chamado de abordagem Top-Down, pois começa dos casos de cima e vai descendo até chegar à raiz da DP. Existe outro método, em que fazemos o contrário: construimos os casos base e a partir dele vamos criando os casos mais de cima, até que cheguemos no caso procurado. Esse tipo de abordagem é conhecido como Bottom-Up.

No problema de Fibonacci, isso seria semelhante a criar um vetor de n posições de nome int fib, por exemplo, inicializá-lo com os casos base já feitos ("fib[0]=0; fib[1]=1;") e então usarmos um for para percorrê-lo até n, fazendo com que cada posição i receba a soma dos valores guardador nas duas posições anteriores ("fib[i]=fib[i-1]+fib[i-2];"). Ao final do for,bastaria imprimir o valor salvo em fib[n]. Como vamos apenas percorrer o vetor uma vez, a complexidade continua O(n). Segue o código para melhor entendimento:

Os programas aqui fornecidos retornam os valores da sequência em O(n), mas para usarmos isso, ou seja, chamarmos numeros de Fibonacci em posições por volta de 60, precisamos guardar valores maiores que um int. A variável int só guarda inteiros de 32-bit, ou seja, entre $-2^{31}$ e $+2^{31}-1$ (algo um pouco maior que 2 bilhões), mas a sequência de Fibonacci cresce muito rápido. Se quisermos chamar os números grandes de Fibonacci, teremos que guardar os valores (bem como declarar a função) do tipo long long int, que guarda inteiros de 64-bit (algo perto de $10^{18}$ , positivos e negativos). A última observação é que a complexidade de uma DP, em qualquer caso, é o tamanho do array que vamos usar para guardar seus dados, ou estados, pois cada estado só deverá ser calculado uma única vez, no máximo. Ou seja, se usamos um vetor de tamanho n, a complexidade da DP é O(n). Se usarmos uma matriz nxn, a complexidade fica O(n²).

O Problema da Mochila

O Problema mais clássico de Progração Dinâmica talvez seja o KnapSack, ou o problema da mochila. Se você não o conhece, clique aqui para ler uma maneira possível de enunciá-lo. De maneira geral, um ladrão irá roubar uma casa com uma mochila que suporta um peso s. Ele vê n objetos na casa e sabe estimar o peso p_ie o valor v_i de cada objeto i. Com essas informações, qual o maior valor que o ladrão pode roubar sem rasgar sua mochila? Assim como nesse exemplo, Programação Dinâmica é muito comum em problemas que parecem ser resolvidos por algoritmos gulosos, mas não podem. No caso, o primeiro pensamento de alguém pode ser sempre pegar o objeto de maior valor que ainda não foi colocado na mochila, até que não caiba mais nenhum, mas essa ideia é facilmente quebrada com o seguinte exemplo, que segue o modelo de entrada explicado no link acima:

4 3

3 7

2 4

O programa guloso iria preferir o objeto mais valioso (1, de valor 7) e não caberá nenhum dos outros dois. Porém, é melhor que coloquemos na mochila os objetos 2 e 3, que somados têm peso 4 (cabe na mochila) e valor 8 (maior que 7). Depois de pensar um pouco mais, você pode pensar na "densidade de valor" do objeto. Faria um guloso que pusesse na mochila os objetos de maior "valor por grama". Porém, o mesmo caso de entrada mostrado acima mostra que esse guloso tomaria a mesma decisão errada que o outro. O que fazer então? Uma DP! Vale ressaltar que, na maioria das vezes (inclusive agora), faremos uma DP Top-Down por ser mais fácil e didática que a Bottom-Up.

Vamos criar dois vetores apenas para guardarmos o peso e o valor de cada objeto, assim, o peso do objeto i estará salvo em peso[i], e o seu valor estará em valor[i]. Para responder o problema, tente pensar em um estado da DP como: estando os objetos em fila, qual o máximo que o ladrão pode roubar se ainda tiver disponível todos os objetos a partir de uma certa posição obj da fila, e a mochila ainda aguentar o peso aguenta sem rasgar, ou seja, tente implementar a função int knapsack(int obj, int aguenta){}. Ela deverá receber o número do objeto que está sendo verificado e quanto peso a mochila ainda aguenta, retornando, para tais parâmetros, o maior valor que que o ladrão pode roubar se ainda sobrar aguenta gramas na mochila e você puder colocar ou não colocar todos os objetos a partir de obj. A ideia é, dados os objetos em fila, em ordem qualquer de entrada, testá-los, um a um, se é melhor colocá-lo, ou não, testando todas as possibilidades com um DP. Para isso basta analisarmos o estado em que a DP ficaria se colocássemos e se não colocássemos o objeto que estamos olhando, e escolher o melhor deles.

Em uma DP, antes de qualquer coisa, veremos se o estado que estamos olhando já foi calculado, ou seja, se em algum momento já chamamos a função para os parâmetros atuais ("dp(obj, aguenta)"). Se isso ocorrer, deverá estar salvo na nossa tabela de DP, de nome tab, nos índices obj e aguenta. Vamos inicializá-la com todos os valores iguais a -1 com o memset e quando calcularmos algum valor, vamos substituí-lo na tabela, ou seja, se o valor salvo nela, para os parâmetros que estamos olhando, for maior ou igual a zero ("if(tab[obj][aguenta]>=0)") retornamos o valor que está salvo lá ("return tab[obj][aguenta];").

As bases da DP são duas: se já olharmos todos os objetos da fila, ou seja, já estamos em uma posição maior que n ("if(obj>n)"), ou se ela não aguentar mais peso algum ("if(aguenta==0)"), não podemos mais adicionar nada na mochila, ou seja, a função deve retornar valor 0.

Nos demais casos da DP, temos que olhar se o melhor é colocar ou não o objeto, então vejamos o que ocorrer nos dois casos! Vamos declarar o int nao_coloca, que receberá o maior valor que podemos obter sem colocar obj na mochila, e testando todos os outros da fila. Assim, o estado em que ficaremos seria: vamos olhar o próximo objeto (obj+1) e a mochila continuará ainda aguentando o mesmo que antes, pois não colocamos obj na mochila, logo, executamos o comando "nao_coloca=knapsack(obj+1, aguenta);". Agora, vamos testar se é possível colocar obj, ou seja, se o peso de obj não é maior que o peso que a mochila aguenta ("if(peso[obj]<=aguenta)"). Se for possível, devemos retornar que o máximo que podemos obter equivale ao valor do objeto que colocamos somado do melhor que podemos testando o próximo objeto, sendo que agora a mochila aguentará o que ela aguentava antes, subtraído do peso de obj. Em outras palavras, criaríamos a variável int coloca e atribuiríamos a ela o valor valor[obj]+knapsack(obj+1, aguenta-peso[obj). Feito isso, retornamos o melhor, ou seja, o maior valor dentre o de colocar ou não colocar obj na mochila. Para isso, usaremos a função max da biblioteca de C++ algorithm, que recebe dois objetos quaisquer como parâmetros e retorna o maior deles, segundo os operadores "<" e ">". Retornaremos, portanto o maior dentre coloca e nao_coloca, lembrando de salvar antes o valor na tabela de DP ("return tab[obj][aguenta]=max(coloca, nao_coloca;").

Caso a função continue sua execução sem retornar, então não foi possível colocar o objeto e só temos uma opção: não colocá-lo, logo a função deve retornar o valor de nao_coloca, também salvando-o antes na tabela de DP. Assim, basta lemos todos os pesos e valores dos objetos na entrada e depois retornarmos o melhor possível dentre colocar ou não o primeiro objeto da fila, sendo que a mochila ainda aguenta seu valor inicial s, ou seja, devemos imprimir o valor de knapsack(1, s). Segue o código comentado para melhor entendimento:

Você deve levar a ideia do problema da mochila, de testar todas as possibilidades de maneira eficiente, com você para o resto da vida. Muitos problemas de DP são resolvidos nesse estilo.

Maior Subsequência Comum

Este é outro problema muito clássico de Programação Dinâmica e que deve permanecer na sua cabeça enquanto você participar de competições de programação. Dadas duas sequências s₁e s₂, uma de tamanho n e outra de tamanho m, qual a maior subsequência comum às duas? Lembre-se que uma subsequência de s₁,por exemplo, não precisa ter seus membros adjacentes também adjacentes em s₁. Isto significa que {1, 3, 5} é uma subsequência de {1, 2, 3, 4, 5}, mesmo 1 não estando do lado do 3 na sequência original. A entrada terá três linhas Pense um pouco: que parâmetros você escolheria para serem os parâmetros da DP? Se teve uma boa ideia, experimente implementá-la, se não seguem a explicação e o código comentado.

Uma ótima ideia para representarmos os estados da DP são os finais das sequências. Ou seja, implemente uma função lcs (Longest Common Subsequence) que receba dois inteiros a e b e retorne a maior subsequência comum entre os a primeiros elementos de s1 e os b primeiros elementos de s2. Assim, seja s1={1, 2, 3, 4, 5} e s2={1, 0, 3, -2, 5, 7}. A maior subsequência comum entre elas duas é {1, 3, 5}, pois estamos considerado todos os seu elementos, ou seja, como s1 tem 5 elementos e s2 tem 6, lcs(5, 6) retorna 3, que é o comprimento de {1, 3, 5}. Porém, se quiséssemos comparar a sequências só até o 3º termo da primeira e o 4º termo da segunda, ou seja, quiséssemos comparar as sequências {1, 2, 3} e {1, 0, 3, -2}, a maior subsequência comum a elas é {1, 3}, com dois elementos, logo lcs(3, 4) retorna 2.

Imagine que a entrada do problema consiste de três linhas: na primeira estão os inteiros n e m e, nas outras duas seguem n e m inteiros: os elementos de s1 e s2, respectivamente. O programa deve gerar como saída uma única linha com o valor da maior subsequência comum a s1 e s2. Segue um exemplo de entrada e um de saída:

Entrada:

5 6

1 2 3 4 5

1 0 3 -2 5 7

Saída:

Vamos salvar os elementos de s1 no vetor int s1[MAXN] e os de s2 no vetor int s2[MAXN], onde MAXN é o tamanho máximo das sequências. No caso, vamos definir o valor de MAXN como 1000.

Antes de tudo, lembre-se de salvar os resultados anteriores da função em uma tabela de DP, de nome tab por exemplo, onde termos o resultado de lcs(a,b) salvo em tab[a][b]. Ela começará com todos os valores iguais a -1, indicando nenhum deles foi calculado ainda. Assim, sempre no começo da função, cheque se aquele estado que você está calculando ainda não foi calculado. Se tiver sido, retorne o valor que você tem salvo para ele.

Desse modo, vamos pensar nos casos bases da DP. É possível calcular o valor da função instantaneamente se a=0 ou se b=0, pois não é possível que haja subsequência de comprimento positivo em uma sequência de nenhum elemento, logo, nesses dois casos, a função deve retornar 0, e guardar o resultado na tabela de DP.

Vejamos agora o caso geral da função. Vamos calcular o valor de lcs(a, b). Cheque se o a-ésimo elemento de s1 é igual ao b-ésimo elemento de s2 ("if(s1[a]==s2[b])"). Se eles forem iguais, então a maior subsequência será exatamente um elemento maior que a maior subsequência entre os a-1 primeiros elementos de s1 e o b-1 primeiros elementos de s2 (pois será exatamente ela somada ao novo elemento comum encontrado, que é s1[a]==s2[b]). Caso contrário, temos duas possibilidades:

A maior subsequência comum termina exatamente no elemento s1[a]. Nesse caso, sabemos que s2[b] não está nela, pois se estivesse, ela terminaria exatamente em s2[b], visto que ele é o último elemento considerado de s2. Assim, não faz nenhuma diferença removermos esse elemento de s2 e recalcularmos a comparação, pois a lcs continuará a mesma. Assim, podemos retornar o valor de lcs(a, b-1), e salvá-lo na tabela de DP.
A maior subsequência comum não termina no elemento s1[a]. Nesse caso, sabemos que s1[a] não nela, pelo mesmo motivo que s2[b] não estaria, no exemplo anterior. Desse modo, não faz nenhuma diferença removermos s1[a] de s1 e recalcularmos a comparação, pois a lcs continuará a mesma. Assim, podemos retornar o valor de lcs(a-1, b), e salvá-lo na tabela de DP.

Dentre as duas possibilidades, retornamos a maior delas! Agora basta implementarmos a função com essa recursão, lermos os tamanhos e elementos de s1 e s2 e imprimirmos o valor de lcs(n, m), para considerarmos a maior subsequência comum a todos os elementos de s1 e s2. Segue o código comentado para maior entendimento:

Uma outra aplicação para a função lcs é a de encontrar a maior subsequência crescente, ou lis (Longest Increasing Subsequence) em O(n²). Para isso, basta reproduzirmos a sequência em um segundo vetor, ordená-lo, e comparar a sequência original com a ordenada, chamando a função lis. A maior subsequência comum a uma sequência e sua versão ordenada é a maior subsequência ordenada da original. Segue o código para melhor entendimento:

Vale lembrar que uma sequência crescente é uma que não decresce, visto que um vetor ordenado tem a mesma definição (o sort não exclui elementos repetidos).

Agora que você já sabe tudo isso de DP, tente fazer os problemas abaixo. Se você não conseguir resolver algum deles, ou surgir dúvida na teoria apresentada na aula, volte para a página inicial do curso para preencher o formulário e nos enviar sua dúvida.

Problema 1 - Comparação de Substring (Note que esse não é o problema resolvido na aula. Clique aqui para ver o que é uma substring)

Problema 2 - Pontes de São Petesburgo (Problema com solução do Noic! Para vê-la clique aqui)

Problema 3 - Motoboy

Problema 4 - Troco (problema da 2ª fase da P1 da OBI 2013, com solução do Noic! Para vê-la clique aqui)

Problema 5 - Festival de Estátuas de Gelo

Problema 6 - Baile de Formatura

Problema 7 - Ajude Bob

As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.