Artigo original: Demystifying Dynamic Programming

Escrito por: Alaina Kafkes

Como criar e programar algoritmos em programação dinâmica

Talvez você tenha ouvido falar sobre isso na preparação para entrevistas de programação. Talvez você a tenha enfrentado em um curso de algoritmos. Talvez você esteja tentando aprender a programar por conta própria e tenha descoberto em algum lugar que é importante entender a programação dinâmica. Usar programação dinâmica (ou DP, do inglês, dynamic programming) para escrever algoritmos é importante e, ao mesmo tempo, assustador.

Quem pode culpar aqueles que se esquivam dela? A programação dinâmica parece intimidante porque é mal ensinada. Muitos tutoriais se concentram no resultado – explicando o algoritmo, em vez do processo – que é encontrar o algoritmo . Isso incentiva os alunos a decorar/memorizar , não a compreender.

Durante minha aula de algoritmos este ano, montei meu próprio processo para resolver problemas que exigem programação dinâmica. Partes desse processo vêm do meu professor de algoritmos (a quem eu devo muito por esse entendimento!) e partes vêm da minha própria análise aprofundada de algoritmos de programação dinâmica.

Antes de compartilhar meu processo, no entanto, vamos começar com o básico. O que é a programação dinâmica?

Definição de programação dinâmica

A programação dinâmica tem a ver com dividir um problema de otimização em subproblemas mais simples e armazenar a solução para cada subproblema de modo que cada subproblema seja resolvido apenas uma vez.

Para falar a verdade, essa definição pode não fazer todo o sentido até que você veja um exemplo de um subproblema. Tudo bem. Esse exemplo virá na próxima seção.

O que espero transmitir é que a DP é uma técnica útil para problemas de otimização, aqueles problemas que buscam a solução máxima ou mínima dadas certas restrições, porque examina todos os subproblemas possíveis e nunca recalcula a solução para qualquer subproblema. Isso garante correção e eficiência, o que não podemos dizer da maioria das técnicas usadas para algoritmos de resolução ou tratamento de um problema. Isso, por si só, torna a DP especial.

Nas próximas duas seções, explicarei o que é um subproblema e, em seguida, explicarei por que armazenar soluções — uma técnica conhecida como memoização — é importante na programação dinâmica.

Subproblemas em subproblemas em subproblemas

Os subproblemas são versões menores do problema original. Na verdade, os subproblemas geralmente parecem uma versão reformulada do problema original. Se formulados corretamente, os subproblemas se acumulam para obter a solução para o problema original.

Para dar uma ideia melhor de como isso funciona, vamos encontrar o subproblema em um exemplo de problema de programação dinâmica.

Faça de conta que você está de volta à década de 1950 trabalhando em um computador IBM-650. Você sabe o que isso significa – cartões perfurados! Seu trabalho é lidar com o IBM-650 por um dia. Você recebe um número natural n de cartões perfurados para executar. Cada cartão perfurado deve ser executado em algum horário de início predeterminado s_i e parar de funcionar em algum horário de término predeterminado f_i. Apenas um cartão perfurado pode ser executado no IBM-650 de cada vez. Cada cartão perfurado também tem um valor associado v_i com base em sua importância para a empresa.

Problema: como responsável pelo IBM-650, você deve determinar o cronograma ideal de cartões perfurados que maximize o valor total de todos os cartões perfurados executados.

Como vou passar por esse exemplo em detalhes no decorrer deste artigo, vou apenas provocá-lo com seu subproblema por enquanto:

Subproblema: estabelecer o cronograma de valor máximo para cartões perfurados de i a n, de modo que os cartões perfurados sejam classificados por hora de início.

Observe como o subproblema divide o problema original em componentes que constroem a solução. Com o subproblema, você pode encontrar o cronograma de valor máximo para cartões perfurados n-1 a n e, em seguida, para cartões perfurados n-2 a n e assim por diante. Ao encontrar as soluções para cada subproblema, você pode resolver o problema original em si: o cronograma de valor máximo para cartões perfurados de 1 a n. Como o subproblema se parece com o problema original, os subproblemas podem ser usados para resolver o problema original.

Na programação dinâmica, depois de resolver cada subproblema, você deve memorizá-lo ou armazená-lo. Vamos descobrir o porquê na seção a seguir.

Motivação para a memoização com os números da sequência de Fibonacci

Ao receber a instrução de implementar um algoritmo que calcule o valor de Fibonacci (texto em inglês) para determinado número, o que você faria? A maioria das pessoas que eu conheço escolheria um algoritmo recursivo (texto em inglês). Um algoritmo assim teria esta aparência em Python:

def fibonacciVal(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fibonacciVal(n-1) + fibonacciVal(n-2)

Esse é um algoritmo que alcança seu objetivo, mas o custo para isso é enorme. Por exemplo, vamos examinar o que o algoritmo faz quando precisa calcular o valor de Fibonacci para n = 5 (abreviado como F(5)).

Cada cálculo deve ser feito na ordem para encontrar o valor de Fibonacci para n = 5. O subproblema para n = 2, por exemplo, é resolvido três vezes. Para um exemplo relativamente pequeno (n = 5), é uma quantidade de cálculos excessivamente repetida e desperdiçada!

Se, ao invés de calcular o valor de Fibonacci para n = 2 três vezes, criássemos um algoritmo que calcula o valor uma vez, armazena-o e acessa o valor armazenado para toda e qualquer ocorrência posterior de n = 2, teríamos uma melhoria e tanto, não? É exatamente isso que a memoização faz.

Com isso em mente, escrevi uma solução usando programação dinâmica para o problema do valor de Fibonacci:

def fibonacciVal(n):
  memo = [0] * (n+1)
  memo[0], memo[1] = 0, 1
  for i in range(2, n+1):
    memo[i] = memo[i-1] + memo[i-2]
    return memo[n]

Perceba como a solução do valor de retorno vem do array de memoização memo[], que é preenchido iterativamente pelo loop for. "Iterativamente", neste caso, significa que memo[2] é calculado e armazenado antes de memo[3], memo[4], … e memo[n]. Como memo[ ] é preenchido nessa ordem, a solução para cada subproblema (n = 3) pode ser resolvida pelas soluções de seus subproblemas anteriores (n = 2 e n = 1), dado que esses valores já foram armazenados em memo[] anteriormente.

A memoização tem como vantagem tornar desnecessário o recálculo, o que torna o algoritmo mais eficiente. Desse modo, a memoização garante que a programação dinâmica é eficiente, mas é a escolha do subproblema certo que garante que um "programa dinâmico" examine todas as possibilidades para encontrar a melhor.

Agora que tratamos da memoização e dos subproblemas, é o momento de aprender o processo da programação dinâmica em si. Aperte o cinto.

Meu processo de programação dinâmica

Passo 1: identificar o subproblema em palavras.

Com frequência, os programadores começarão a escrever o código antes de exercitar seu pensamento crítico sobre o problema. Isso não é bom. Uma estratégia para botar seu cérebro para funcionar antes mesmo de tocar no teclado é usar palavras no seu próprio idioma para descrever o subproblema que você identificou dentro do problema original.

Se estiver resolvendo um problema que precise da programação dinâmica, pegue um pedaço de papel e pense nas informações necessárias para resolver o problema. Escreva o subproblema tendo isso em consideração.

Por exemplo, no problema dos cartões perfurados, afirmei que o subproblema pode ser escrito como "o cronograma de valor máximo para cartões perfurados de i até n, de modo que os cartões sejam ordenados de acordo com o tempo de início". Eu encontrei esse subproblema ao me dar conta de que, para determinar o cronograma de valor máximo para os cartões perfurados de 1 até n dessa maneira, eu precisaria encontrar a resposta para os seguintes subproblemas:

  • O cronograma de valor máximo para os cartões perfurados de n-1 até n de modo que os cartões sejam ordenados pelo tempo de início
  • O cronograma de valor máximo para os cartões perfurados de n-2 até n de modo que os cartões sejam ordenados pelo tempo de início
  • O cronograma de valor máximo para os cartões perfurados de n-3 até n de modo que os cartões sejam ordenados pelo tempo de início
  • e assim por diante até
  • O cronograma de valor máximo para os cartões perfurados de 2 até n de modo que os cartões sejam ordenados pelo tempo de início

Se você consegue identificar um subproblema que se baseia em subproblemas anteriores para resolver o problema em questão, está no caminho certo.

Passo 2: escrever o subproblema como uma decisão matemática recorrente.

Depois de identificar um subproblema em palavras, é hora de escrevê-lo matematicamente. Por quê? Bem, a recorrência matemática, ou decisão repetida, que você encontrar acabará sendo o que você colocará em seu código. Além disso, ao escrever o subproblema, você examina matematicamente seu subproblema em palavras do Passo 1. Se for difícil colocar seu subproblema do Passo 1 em termos da matemática no seu código, pode ser que ele seja o subproblema errado!

Há duas perguntas que me faço toda vez que tento encontrar uma recorrência:

  • Que decisão eu devo tomar a cada passo?
  • Se meu algoritmo está no passo i, de quais informações eu precisarei para decidir o que fazer no passo i+1? (algumas vezes, temos que: se meu algoritmo está no passo i, de quais informações eu precisei para decidir o que fazer no passo i-1?)

Vamos retornar ao problema dos cartões perfurados e fazer essas perguntas.

Que decisão eu tomo a cada passo? Suponha que os cartões perfurados sejam classificados por hora de início, conforme mencionado anteriormente. Para cada cartão perfurado compatível com o cronograma até o momento (sua hora de início é após a hora de término do cartão perfurado que está sendo executado no momento), o algoritmo deve escolher entre duas opções: executar ou não executar o cartão perfurado.

1_b69mBGpwu6bGJrIlodV6Jw
Este programa dinâmico escolhe entre duas opções a cada passo, como nosso velho amigo, Hamlet – ser ou não ser!

Se meu algoritmo estiver no passo i, de quais informações eu necessito para decidir o que fazer no passo i+1? Para decidir entre as duas opções, o algoritmo precisa saber o próximo cartão perfurado compatível na ordem. O próximo cartão perfurado compatível para um determinado cartão perfurado p é o cartão perfurado q tal que s_q (a hora de início predeterminada para o cartão perfurado q) ocorre após f_p (a hora de término predeterminada para o cartão perfurado p) e a diferença entre s_q e f_p é minimizada. Abandonando a linguagem matemática, o próximo cartão perfurado compatível é aquele com a hora de início mais próxima após o cartão perfurado atual terminar de ser executado.

Se meu algoritmo está no passo i, de quais informações eu precisei para decidir o que fazer no passo i-1? O algoritmo precisa saber sobre decisões futuras: aquelas feitas para os cartões perfurados de i a n para decidir se executa ou não executa o cartão perfurado i-1.

Agora que respondemos a essas perguntas, talvez você tenha começado a formar uma decisão matemática recorrente em sua mente. Caso contrário, tudo bem, fica mais fácil escrever recorrências à medida que você é exposto a problemas de programação mais dinâmicos.

Sem mais delongas, aqui está nossa recorrência:

OPT(i) = max(v_i + OPT(proximo[i]), OPT(i+1))

Essa recorrência matemática requer alguma explicação, especialmente para aqueles que não escreveram uma antes. Eu uso OPT (i) para representar o cronograma do valor máximo para cartões perfurados de i a n, de modo que os cartões perfurados sejam classificados por hora de início. Parece familiar, certo? OPT(•) é nosso subproblema do Passo 1.

Para determinar o valor de OPT(i), consideramos duas opções e queremos aproveitar ao máximo essas opções para atingir nossa meta: o cronograma de valor máximo para todos os cartões perfurados. Uma vez que escolhemos a opção que dá o resultado máximo na etapa i, memorizamos seu valor como OPT(i).

As duas opções — executar ou não o cartão perfurado i — são representadas matematicamente assim:

v_i + OPT(proximo[i])

Esta sentença representa a decisão de executar o cartão perfurado i. Ela adiciona o valor obtido com a execução do cartão perfurado i para OPT(proximo[i]), onde proximo[i] representa o próximo cartão perfurado compatível após o cartão perfurado i. OPT(proximo[i]) fornece o agendamento de valor máximo para cartões perfurados proximo[i] a n, de modo que os cartões perfurados sejam classificados por hora de início. A soma desses dois valores produz o agendamento de valor máximo para cartões perfurados de i a n, de modo que os cartões perfurados sejam classificados por hora de início se o cartão perfurado i for executado.

OPT(i+1)

Por outro lado, esta sentença representa a decisão de não executar o cartão perfurado i. Se o cartão perfurado i não for executado, seu valor não será obtido. OPT(i+1) fornece o agendamento de valor máximo para cartões perfurados i+1 a n, de modo que os cartões perfurados sejam classificados por hora de início. Portanto, OPT(i+1) fornece o cronograma de valor máximo para cartões perfurados i a n, de modo que os cartões perfurados sejam classificados por hora de início se o cartão perfurado i não for executado.

Desse modo, a decisão tomada a cada passo dos problemas dos cartões perfurados é codificada matematicamente para refletir o subproblema do Passo 1.

Passo 3: resolver o problema original usando os passos 1 e 2.

No passo 1, escrevemos o subproblema do problema do cartão perfurado em palavras. No passo 2, escrevemos uma decisão matemática recorrente que corresponde a esses subproblemas. Como podemos resolver o problema original com essas informações?

OPT(1)

É simples assim. Como o subproblema que encontramos no passo 1 é o cronograma de valor máximo para cartões perfurados de i a n, de modo que os cartões perfurados sejam classificados por hora de início, podemos escrever a solução para o problema original como o cronograma de valor máximo para cartões perfurados de 1 a n, de modo que os cartões perfurados sejam classificados por hora de início. Como os passos 1 e 2 andam de mãos dadas, o problema original também pode ser escrito como OPT(1).

Passo 4: determinar as dimensões do array de memoização e a direção na qual ele deve ser preenchido.

Achou o passo 3 simples demais para ser verdade? Com certeza, ele dá essa impressão. Você pode se perguntar como OPT(1) pode ser a solução para nosso programa dinâmico se ele depende de OPT(2), OPT(proximo[1]) e assim por diante?

Você está correto em perceber que OPT(1) depende da solução de OPT(2). Isso vem diretamente após o passo 2:

OPT(1) = max(v_1 + OPT(proximo[1]), OPT(2))

Essa, porém, não é uma questão terrível. Pense no exemplo de memoização de Fibonacci. Para encontrar o valor de Fibonacci para n = 5, o algoritmo se baseia no fato de que os valores de Fibonacci para n = 4, n = 3, n = 2, n = 1 e n = 0 já foram memoizados. Se preenchermos nossa tabela de memoização na ordem correta, a dependência que OPT(1) tem dos outros subproblemas não é grande coisa.

Como podemos identificar a direção correta para preencher a tabela de memoização? No problema do cartão perfurado, uma vez que sabemos que OPT(1) depende das soluções para OPT(2) e OPT (proximo[1]), e que os cartões perfurados 2 e proximos[1] têm horários de início após o cartão perfurado 1 devido à classificação, podemos inferir que precisamos preencher nossa tabela de memoização de OPT (n) para OPT (1).

Como determinamos as dimensões desse array de memoização? Aqui está um truque: as dimensões do array são iguais ao número e tamanho das variáveis das quais OPT(•) depende. No problema do cartão perfurado, temos OPT(i), o que significa que OPT(•) depende apenas da variável i, que representa o número do cartão perfurado. Isso sugere que nosso array de memoização será unidimensional e que seu tamanho será n, pois há n cartões perfurados no total.

Se soubermos que n= 5, então nosso array de memoização pode ficar assim:

memo = [OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

Porém, como a maioria das linguagens de programação inicia a indexação de arrays em 0 (texto em inglês), pode ser mais conveniente criar esse array de memoização para que seus índices se alinhem com os números de cartões perfurados:

memo = [0, OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

Passo 5: programar!

Para programar nosso programa dinâmico, reunimos os passos de 2 a 4. A única informação nova de que você precisará para escrever um programa dinâmico é um caso base, que você pode encontrar ao mexer em seu algoritmo.

Um programa dinâmico para o problema do cartão perfurado será mais ou menos assim:

def punchcardSchedule(n, valores, proximo): # Inicia o array de memoização - passo 4
    memo = [0] * (n+1)   # Define o caso base
    memo[n] = valores[n]   # Cria a tabela de memoização de n a 1 - passo 2
    for i in range(n-1, 0, -1):
        memo[i] = max(v_i + memo[proximo[i]], memo[i+1])  # Retorna a solução do problema original OPT(1) - passo 3
	return memo[1]

Parabéns por escrever seu primeiro programa dinâmico! Agora que você iniciou os trabalhos, vou mostrar para você em um tipo diferente de programa dinâmico.

Paradoxo da escolha: exemplo de programação dinâmica com múltiplas opções

1_ZOy2VkYyok5a5YoBEUGMtg
Na imagem: "Alô? Preciso de ajuda para escolher uma linha de ajuda." – não relacionado à programação dinâmica, mas uma ilustração clara de como ter decisões de múltipla escolha pode se tornar um desafio rapidamente.

Embora o exemplo anterior de programação dinâmica tivesse uma decisão de duas opções — executar ou não executar um cartão perfurado — alguns problemas exigem que várias opções sejam consideradas antes que uma decisão possa ser tomada em cada etapa.

É hora de um novo exemplo.

Faça de conta que você está vendendo as pulseiras da amizade para n clientes, e que o valor desse produto aumenta monotonicamente. Isso significa que o produto tem preços {p_1, ..., p_n} tais que p_i ≤ p_j se o cliente j vier depois do cliente i. Esses n clientes têm valores {v_1, ..., v_n}. Um determinado cliente i comprará uma pulseira da amizade pelo preço p_i se e somente se  p_i ≤ v_i; caso contrário, a receita obtida desse cliente será 0. Suponha que os preços sejam números naturais.

Problema: você deve encontrar o conjunto de preços que garanta a máxima receita possível com a venda de suas pulseiras da amizade.

Reserve um segundo para pensar em como você pode resolver esse problema antes de examinar minhas soluções para os passos 1 e 2.

Passo 1: identificar o subproblema em palavras.

Subproblema: a receita máxima obtida de clientes de i a n de modo que o preço para o cliente  i-1 tenha sido definido em q.

Encontrei esse subproblema percebendo que, para determinar a receita máxima para os clientes de 1 a n, precisaria encontrar a resposta para os seguintes subproblemas:

  • A receita máxima obtida dos clientes n-1 a n de modo que o preço do cliente n-2 tenha sido definido em q.
  • A receita máxima obtida dos clientes n-2 a n de modo que o preço do cliente n-3 tenha sido definido em q.
  • (e assim por diante)

Observe que introduzi uma segunda variável q no subproblema. Fiz isso porque, para resolver cada subproblema, preciso saber o preço que estabeleci para o cliente antes desse subproblema. A variável q garante a natureza monotônica do conjunto de preços, enquanto a variável i mantém o controle do cliente atual.

Passo 2: escrever o subproblema como uma decisão matemática recorrente.

Há duas perguntas que me faço toda vez que tento encontrar uma recorrência:

  • Que decisão preciso tomar a cada passo?
  • Se meu algoritmo está no passo i, de quais informações eu precisarei para decidir o que fazer no passo i+1? (algumas vezes, temos que: se meu algoritmo está no passo i, de quais informações eu precisei para decidir o que fazer no passo i-1?)

Vamos voltar ao problema da pulseira da amizade e fazer essas perguntas.

Que decisão eu tomo a cada passo? Eu decido a que preço vender minha pulseira da amizade para o cliente atual. Como os preços devem ser números naturais, sei que devo definir meu preço para o cliente i na faixa de q – o preço definido para o cliente i-1 – a v_i – o preço máximo pelo qual o cliente comprará uma pulseira da amizade.

Se meu algoritmo estiver na etapa i, quais informações ele precisaria para decidir o que fazer na etapa i + 1? Meu algoritmo precisa saber o preço definido para o cliente i e o valor do cliente i+1 para decidir em qual número natural definir o preço para o cliente i+1.

Com esse conhecimento, posso escrever matematicamente a recorrência:

OPT(i,q) = max~([Receita(v_i, a) + OPT(i+1, a)])
de modo que max~ encontra o máximo entre todos os a no intervalo q ≤ a ≤ v_i

Mais uma vez, essa recorrência matemática requer alguma explicação. Como o preço para o cliente i-1 é q, para o cliente i, o preço a permanece no inteiro q ou muda para algum inteiro entre q+1 e v_i. Para encontrar a receita total, adicionamos a receita do cliente i à receita máxima obtida dos clientes i+1 a n, de modo que o preço do cliente i foi definido em a.

Em outras palavras, para maximizar a receita total, o algoritmo deve encontrar o preço ideal para o cliente i, verificando todos os preços possíveis entre q e v_i. Se v_i ≤ q, então o preço a deve permanecer em q.

E quanto aos outros passos?

Ao trabalharmos os passos 1 e 2, temos a parte mais difícil da programação dinâmica. Como exercídio, sugiro que você faça os passos 3, 4 e 5 por conta própria para ver se entendeu.

Análise em tempo real dos programas dinâmicos

Agora, vamos à parte divertida de escrever algoritmos: a análise do tempo de execução. Usarei a notação big-O ao longo dessa discussão. Se você ainda não está familiarizado com o big-O, sugiro que leia sobre ele aqui (texto em inglês).

Geralmente, o tempo de execução de um programa dinâmico é composto pelos seguintes recursos:

  • Pré-processamento
  • Quantas vezes o loop for é executado
  • Quanto tempo leva para a recorrência ser executada em uma iteração do loop for
  • Pós-processamento

No geral, o tempo de execução assume a seguinte forma:

Pré-processamento + Loop * Recorrência + Pós-processamento

Vamos realizar uma análise de tempo de execução do problema do cartão perfurado para nos familiarizarmos com o big-O para programas dinâmicos. Aqui está o programa dinâmico do problema do cartão perfurado:

def punchcardSchedule(n, valores, proximo): # Inicia o array de memoização - passo 4
	memo = [0] * (n+1)   # Define o caso de base
    memo[n] = valores[n]   # Cria a tabela de memoização de n a 1 - passo 2
    for i in range(n-1, 0, -1):
    	memo[i] = max(v_i + memo[proximo[i]], memo[i+1])  # Retorna a solução para o problema original OPT(1) - passo 3
    return memo[1]

Vamos detalhar seu tempo de execução:

  • Pré-processamento: aqui, isso significa construir o array de memoização. O(n).
  • Quantas vezes o loop for é executado: O(n).
  • Quanto tempo leva para a recorrência ser executada em uma iteração do loop for: a recorrência leva tempo constante para ser executada porque toma uma decisão entre duas opções em cada iteração. O(1).
  • Pós-processamento: nada ocorre aqui! O(1).

O tempo de execução geral do programa dinâmico do problema do cartão perfurado é O(n) O(n) * O(1) + O(1), ou, de modo simplificado, O(n).

Você chegou lá!

É isso — você está um passo mais perto de se tornar um gênio da programação dinâmica!

1_iFMwuyC5ym3f_Ep6L_GEEA
Margaret Hamilton: uma das várias mestres da programação da nossa história!

Um último conselho: continue praticando programação dinâmica. Não importa o nível de frustração que esses algoritmos possam parecer ter, escrever repetidamente programas dinâmicos fará com que os subproblemas e recorrências cheguem até você com mais naturalidade. Aqui está uma lista de crowdsourcing de problemas clássicos de programação dinâmica (texto em inglês) para você experimentar.

Então, faça suas entrevistas, suas aulas e viva (logicamente) com seu novo conhecimento de programação dinâmica!

Agradeço muito a Steven Bennett, Claire Durand e Prithaj Nath por terem revisado este artigo originalmente. Agradeço também ao Professor Hartline por me empolgar com a ideia de aprender sobre programação dinâmica ao ponto de me fazer escrever tanto sobre ela.

Gostou do que leu? Compartilhe este artigo. Tem sugestões ou perguntas? Entre em contato com a autora pelo Twitter (em inglês).