Pular para o conteúdo

O que é programação dinâmica?

Aula 1 de 20 · 5 min

O que é programação dinâmica?

Passo 1 de 10

Merge sort em [5, 2, 9, 1]: divida ao meio, duas vezes, até cada pedaço ser um único valor.

A ideia

A programação dinâmica se aplica quando duas coisas são verdade: o mesmo subproblema reaparece o tempo todo, e a melhor resposta completa é montada com as melhores sub-respostas. O merge sort divide em metades novas que nunca se sobrepõem, então o cache não rende nada. Os ramos de Fibonacci colidem sem parar, então o cache rende tudo. Você já fez isso à mão na aula de memoização — DP é esse hábito, agora de propósito.

Exemplo do mundo real

Uma confeitaria calculando o custo do cardápio de bolos. Metade das receitas usa o mesmo buttercream, então o confeiteiro calcula o preço de uma leva dele uma única vez e prende o valor na parede. Todo bolo que leva buttercream lê esse número em vez de recalcular manteiga, açúcar e mão de obra do zero.

O código

Sua vez

O que isto imprime?

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
  return n if n < 2 else f(n - 1) + f(n - 2)

f(10)
print(f.cache_info().misses)

Mini quiz

1 / 3

Que par de propriedades faz de um problema um problema de DP?