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