Programação Dinâmica 01 - Introdução a Programação Dinâmica

Escrito por Luca Dantas

Baseado originalmente na aula por Rogério Júnior

Motivação inicial

A sequência de Fibonacci

Na aula de funções vimos como calcular o n-ésimo elemento da sequência de Fibonacci. Foi mostrada também a árvore de recursão criada para calcular o 5º número da sequência de Fibonacci, que mostra todas as chamadas feitas por essa função. Reveja:

Note que o $Fib(2)$, por exemplo, é calculado $3$ vezes na árvore, e cada uma dessas chamadas gera o recálculo de $Fib(1)$ e $Fib(0)$. Você percebe como sempre chamar a recursão é ineficiente? O número de chamadas em uma função que calcula o Fibonacci cresce exponencialmente, de modo que a maioria dos computadores não consegue calcular em tempo razoável valores maiores do que 50.

Imagine que estamos fazendo uma chamada à função $Fib(5)$: ela teria que chamar todos os 14 valores de $Fib$ mostrados na árvore acima, independentemente se esse valor já foi calculado anteriormente ou não. Mas o que aconteceria se salvássemos o valor de $Fib(5)$ em algum lugar depois que o calculamos pela primeira vez? Assim, da próxima vez que precisássemos do valor de $Fib(5)$, teríamos ele guardado e poderíamos acessar e retornar seu valor em $O(1)$ ao invés de percorrer toda a árvore mostrada acima! Perceba que esse processo de salvar os valores já calculados pode ser expandido facilmente para os outros valores de $n$, de modo que nenhum estado precisará ser calculado mais de uma vez e teremos uma maneira mais eficiente de calcular essa função.

Vamos tentar implementar essa ideia para calcular 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 queremos calcular. Também vamos definir outro vetor auxiliar bool mark[maxn] para definir se cada estado da DP já foi calculado ou não, assim poderemos checar se devemos somente retornar o valor já calculado ou calculá-lo agora. Agora basta refazer a função fib fazendo-a verificar se já calculei esse estado com "if(mark[x] == 1)", e retornar o valor já salvo em dp[x] caso isso ocorra. Caso eu ainda não tenha calculado esse valor, utilizo a mesma função recursiva e salvo o valor calculado em dp[x] antes de retornar a função, marcando o estado como visitado em mark[x]. 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 encontra algum estado já calculado:

Mas o que é Programação Dinâmica?

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 já obtidos até então e calculando o valor da função apenas se ele nunca foi calculado, exatamente como fizemos no exemplo da sequência de Fibonacci. Assim só calculamos cada valor da função uma única vez!

Podemos perceber que essa técnica é bem geral e é aí que mora o seu poder para resolver problemas. Ela pode ser aplicada desde situações simples como para calcular um termo da sequência de Fibonacci até os problemas mais difíceis das olimpíadas internacionais de informática, o que pode fazer você se perguntar como uma técnica tão direta pode ser cobrada em competições tão difíceis. Isso acontece pois a parte mais interessante desses problemas não consiste na aplicação direta da técnica e sim na construção de uma função que nos permita calcular eficientemente o valor desejado no problema. Note que no problema da sequência de Fibonacci essa função já nos foi dada e portanto é considerado um problema simples.

E em que tipos de problema podemos usar Programação Dinâmica?

Essa técnica é melhor empregada em uma grande classe de problemas as vezes chamados de problemas de Otimização combinatória, ou seja, temos um tipo de construção combinatória que satisfaz um conjunto de regras dadas e queremos extrair algum tipo de informação sobre esse conjunto, como por exemplo quantos conjuntos totais existem que satisfazem as regras dadas, qual o melhor/pior conjunto de acordo com uma função de custo também dada (essa função pode ser por exemplo o tamanho do conjunto ou a soma dos seus elementos), além de existir também casos em que só queremos saber se existe alguma construção dentro desse conjunto que satisfaça alguma outra propriedade especial.

Isso pode ter parecido muito formal e complicado, mas em geral o que queremos com DP é: contar, calcular o máximo/mínimo, saber se algo existe ou não, além de outras ocasiões menos comuns.

Aprendendo a construir uma DP

Estados

Chamaremos de estados da DP os parâmetros que usamos para definir a função. Vamos analisar algumas possibilidades de construção estados da DP com um problema simples. O problema que utilizaremos para a análise é o seguinte:

Temos uma escada com $n$ degraus e um atleta, Pisano. Sabemos que, a partir degrau do $i$, Pisano consegue andar para o degrau $i+1$ ou $i+2$. Nessas condições queremos saber a quantidade de maneiras distintas que Pisano consegue chegar do primeiro até o último degrau (Duas maneiras são distintas se a quantidade de passos dados é diferente ou se existe algum $i$ tal que o i-ésimo passo na primeira sequência é diferente do i-ésimo passo na segunda sequência).

Primeira possibilidade

Poderíamos definir uma função cujo parâmetro é o conjunto de todos valores já visitados nesse caminho, o que seria uma função perfeitamente válida, especialmente se quiséssemos printar todos as possibilidades na tela. Esse método é comumente chamado de força bruta (ou brute force em inglês), pois nós estamos simplesmente gerando todas as possibilidades. Segue uma implementação dessa ideia para melhor entendimento:

Perceba que nesse caso nós não precisamos checar se um estado já foi visitado, pois como nós geramos todos os casos individualmente não existirá nenhum estado que será visitado múltiplas vezes.

Como otimizar essa primeira ideia?

Em geral, o que queremos ter em uma função da DP é encontrar um conjunto de propriedades que nos permita agrupar vários casos em um único estado, e o que precisamos garantir é que quaisquer dois casos que tenham as mesmas propriedades terão a mesma resposta para essa função.

Nesse problema podemos perceber que na realidade a única propriedade que importa para o cálculo da resposta é o último degrau visitado, pois nenhum dos passos seguintes irá interagir com os degraus visitados antes do degrau que estamos atualmente, o que pode ser traduzido como: não importa qual foi a maneira que chegamos no degrau $i$, pois, partindo do degrau $i$, sempre existirá a mesma quantidade de maneiras de se chegar ao degrau $n$.

Desse modo podemos definir uma função que tem como parâmetro somente o último degrau visitado e retornará a quantidade de maneiras de chegar ao degrau $n$ partindo do degrau atual. Formalmente temos que: $f(i) = f(i+1) + f(i+2)$ se $i \leq n-2$, e $f(i) = 1$ se $n-2 < i \leq n$. Perceba que essa é praticamente a mesma função que a definida para a sequência de Fibonacci, portanto o código é muito semelhante, cuja implementação será deixada como um exercício para o leitor.

Transição

A transição de uma DP é o conjunto de possibilidades que temos que considerar para transitar de um estado para o outro. Por exemplo no problema mostrado acima a transição era ir do estado $F(i)$ para $F(i+1)$ ou $F(i+2)$.

Pode ser interessante imaginar o processo de construção da DP como pegar o problema original inteiro, quebrá-lo em pedaços menores e mais fáceis de lidar (os estados), e assim construir as pontes entre esses estados (a transição). Caso você já tenha estudado grafos, esse modo de ver um problema de programação dinâmica se assemelha a um tipo de grafo especial, chamado de DAG, que significa Directed Acyclic Graph, ou Grafo Acíclico Direcionado. Isso está completamente correto, pois a maioria das DPs podem ser representadas como esses grafos especiais e vice-versa, porém quase nunca é otimo visualizar dessa maneira na prática, já que se só virmos o grafo será mais difícil de encontrar propriedades que nos permitam otimizar a DP.

Também é importante notar que a muitas das otimizações que veremos em DPs se encontram na transição, portanto é importante ficar alerta para alguma propriedade especial dela que nos permita otimizar. Não se preocupe agora em saber exatemente como fazê-lo pois abordaremos isso em aulas seguintes.

Um outro aspecto muito importante é que o grafo formado pelas transições seja acíclico, ou seja não é possível que nenhum estado dependa dele mesmo para calcular a resposta, pois caso isso ocorra ficaremos presos num loop infinito e não será possível encontrar uma resposta.

Exercícios

Antes de seguirmos é muito importante entender bem como modelar esses estados da função e como checar se eles realmente estão corretos, visto que encontrar a função correta muitas vezes é a maior parte para resolver o problema. Vale também ressaltar que não existe uma fórmula para encontrar essas funções, porém essa habilidade pode ser adquirida com muita prática com outras questões de DP, pois normalmente existem padrões semelhantes que podem ser ligeiramente modificados e utilizados em outros contextos. Portanto aqui apresentarei alguns exercícios para você tentar modelar por si só e, quando estiver confiante o suficiente em sua ideia, olhar a resposta.

O mais importante com esses exercícios é pensar por si só para entender os problemas e os padrões que neles aparecem, portanto não vá diretamente para as respostas. Recomendo em média 10-20 minutos para cada problema, ou quanto você achar suficiente para entender ter alguma ideia para o problema.

1. Fibonacci cansado

Semelhante ao problema apresentado anteriormente, temos o nosso atleta Pisano, o qual está em uma pista de tamanho $n$ e, partindo da posição $i$, consegue andar para a posição $i+1$ e $i+2$. Porém, em decorrência da escada enfrentada no último problema, Pisano está cansado e não consegue dar dois passos largos seguidos. Formalmente temos: $\nexists i$ tal que $i, i+2, i+4$ estejam presentes na sequência de posições visitadas e $i+1, i+3$ não estejam presentes.

2. Salto Fibonacci

Temos novamente o nosso colega Pisano, dessa vez numa pista de salto com vara. Agora com a ajuda do bastão ele consegue pular desde 1 posição até $k$, que é o tamanho do bastão. Formalmente temos que da posição $i$ ele pode se mover para qualquer uma das posições no intervalo $[i+1, i+k]$. Novamente queremos saber quantas maneiras existem de chegar até o final da pista.

3. Fibonacci ambicioso

Novamente temos o nosso colega Pisano em uma pista de saltos, só que, após ganhar a prova de corrida e a de salto com vara com facilidade, ele se tornou muito ambicioso e agora quer se preparar para a olimpíada, e, para isso, a partir de agora ele só quer enfrentar desafios de dificuldade crescente. Aplicando essa ideia, Pisano decidiu percorrer a pista com uma restrição: Os saltos que ele der têm que ser estritamente maiores que todos os saltos anteriores. Ele também veio treinando bastante seus saltos, portanto consegue pular quantas casas quiser de uma vez só, desde que obedeça a restrição anterior de serem pulos crescentes. Novamente queremos saber quantas maneiras existem de chegar até o final da pista.

Extras para o leitor

Deixarei aqui alguns problemas para você pensar/implementar sozinho porém sem uma resposta escrita. Caso tenham alguma dúvida ou queriam discutir algo sobre eles fiquem livres para acessar o nosso canal do discord e mandar todas as suas dúvidas na seção de informática, ficaremos gratos em ajudar. Porém tente ao máximo pensar neles, já que eles estão sem resposta justamente para você exercitar sua criatividade sem uma resposta fixa.

1. O primeiro exercicio é simplesmente tentar implementar o 3º exercício só que com um limite no intervalo de movimento, ou seja o movimento é limitado ao intervalo $[i+1, i+k]$ e os passos tem de ser crescentes.

2. Imagine novamente o problema igual ao 3º da seção anterior, porém dessa vez temos que os passos têm que ser decrescentes ao invés de crescentes.

3. Agora temos o problema semelhante ao problema inicial com Pisano, no qual so podíamos andar 1 ou 2 degraus por passada, porém dessa vez Pisano encontrou um amigo, o qual está no final da escada. Em cada movimento eles se comunicam e podem decidir qual dos dois vai se mover em cada vez e você tem a missão de descobrir a quantidade de maneiras que eles tem de se encontrar em cada degrau da escada.

Como calcular a complexidade?

Previamente já vimos que a complexidade é uma estimativa de quantas operações faremos em um programa/algoritmo dependendo do tamanho da entrada. Normalmente para problemas de programação dinâmica essa complexidade pode ser estimada como a quantidade de estados da DP (consideramos que visitaremos todos os estados, caso isso não seja verdade provavelmente existe alguma maneira de otimizar a DP para que isso seja verdade) multiplicado pela quantidade máxima de operações que faremos na transição de cada um desses estados. Por exemplo no 2º problema dos exercícios acima temos $O(n)$ estados e em cada um desses estados podemos fazer até $k$ movimentos. Logo a complexidade será $O(nk)$.

É importante observar entretanto que nem sempre esse limite superior na resposta vai refletir a real complexidade, pois existem alguns casos que precisamos faz uma análise do tempo geral somando todos os casos e assim obter uma resposta mais próxima da realidade. Por exemplo, poríamos ter 2 DPs, uma que gasta $n, n/2, n/4, n/8, ...$ e outra que gasta $n, n-1, n-2, n-3,...$, ambos com $log(n)$ elementos. Para o segundo caso a fórmula apresentada anteriormente está correta e a complexidade é $O(n log(n))$, porém no primeiro caso a fórmula geral anterior não está certa e a real complexidade é $O(n)$.

Como exercício volte para os problemas apresentados anteriormente e estime a complexidade da solução apresentada para cada um deles.

Tipos de Abordagem/Implementação

Existem duas principais maneiras de se implementar uma DP. A primeira é a que abordamos durante a maior parte da aula e é a implementação recursiva (algumas vezes também chamada de abordagem Top-Down). Já a segunda é a implementação iterativa, ou seja utilizando alguns for para preencher a matriz ao invés da recursão (algumas vezes também chamada de Bottom-Up). Vamos analisar as vantagens e desvantagens das duas maneiras:

Recursivo:

O método recursivo é normalmente o mais utlizado em aulas introdutórias pois é mais intuitivo e, para problemas simples, pode ter uma implementação mais facil de entender. Por outro lado, a arquitetura dos nossos computadores não é a mais eficiente para realizar recursão, portanto em diversos casos o tempo de execução do programa acaba sendo mais lento, podendo ter problemas com TLE ou MLE em problemas com os limites mais apertados. É recomendado utilizá-lo para se acostumar inicialmente com a ideia de DP e em problemas mais fáceis por sua implementação em geral de mais simples compreensão, porém não é recomendado depender somente dele, visto que em muitos casos a implementação iterativa é necessária.

Iterativo:

O método iterativo normalmente é o método mais utilizado em programação competitiva nos níveis mais altos, o que se deve ao tempo de execução mais rápido (constante menor) e principalmente ao fato de que em muitos problemas somente é possível otimizá-los caso estejamos implementando iterativamente. Além disso, embora seja menos intuitivo as vezes de pensar no código iterativo correto, ele normalmente é menor e mais direto de implementar.

O único ponto que pode ser considerado como negativo pois pode deixar um pouco mais difícil de pensar na implementação é que, como iremos percorrer com um for os estados, precisamos definir anteriormente a ordem correta de percorrer esses itens, pois, caso tenhamos uma ordem incorreta e precisemos do valor de um estado que ainda não calculamos, certamente teremos uma resposta incorreta ao final.

Além disso existem duas maneiras de implementar uma dp iterativa:
Podemos fazer uma pull DP, a qual consiste em, para cada estado, usarmos os valores já calculados dos estados anteriores para atualizar o estado atual.
Podemos também fazer uma push DP, a qual consiste em, para cada cada estado, usarmos o valor que já foi calculado nele para atualizarmos os valores seguintes da DP.

Segue uma implementação iterativa do problema "2. Salto Fibonacci", o qual você pode comparar com a implementação recursiva já mostrada, além de trazer uma implementação Pull e uma Push para comparação. Também iremos mostrar como adendo a otimização prometida anteriormente para esse problema, a qual só pode ser feita na implementação iterativa. Caso não entenda exatamente essa otimização não tem problema, ela não é o mais essencial no momento e fica como um exemplo um pouco mais interessante para os leitores curiosos.

Versão iterativa em $O(nk)$:

Versão iterativa otimizada em $O(n)$:

A ideia para essa otimização é que em cada estado fazemos perguntas a um conjunto de coisas que muda muito pouco, portanto podemos manter o valor que queremos desse conjunto e alterar somente os poucos valores que mudam em cada estado. Nesse caso especificamente sempre perguntamos para o intervalo de tamanho $k$ antes de mim, portanto eu posso simplesmente salvar qual é esse valor anteriormente e quando andarmos para o próximo estado basta remover o i-k elemento e adicionar o i no valor atual.

Outra possibilidade é salvar a soma de prefixo de todas as DPs, desse modo, como queremos saber o valor de um intervalo, basta usarmos o vetor de soma de prefixo com esse fim.

Links externos

Alguns problemas clássicos dos últimos anos da OBI

Bits - OBI 2017

Troco - OBI 2013

Existem também muitos materiais de qualidade que estão em inglês, caso esse não seja um empecilho pode ser muito interessante para você explorá-los, portanto colocarei-os abaixo.

CSES O CSES tem um banco com diversos problemas clássicos, procure a seção de DP e tente resolver o máximo que conseguir.

AtCoder DP Contest Nesse contest estão presentes diversos problemas de DP muito interessantes, desde os mais simples até os que utilizam as técnicas mais avançadas. Recomendo fazer pelo menos do A ao C e tentar do D ao F caso tenha interesse.

Errichto - Introduction to DP Excelente vídeo de introdução a DP. Caso te interesse existem também outros dois vídeos dele no assunto.