GEMA

Memoização

• Guardar os estados que já foram calculados para evitar repetição
• Que nem João e Maria jogando migalhas de pão no chão pra não repetir o caminho e ficar andando em círculos

Tipos de DP

• Top-Down: "de cima pra baixo" → naturalmente recursivo, vai indo do ultimo estado até chegar no caso base
• Bottom-Up: "de baixo pra cima" → naturalmente iterativo, começa no caso base, e vai usando ele pra calcular os próximos.

"Template" básico

O template básico de uma função de DP top-down é bem parecido com a função recursiva, com exceção da parte de memoização

int solve(estado) {
   if (memo[estado] ja visitado) return memo[estado];
   if (caso base) return resposta caso base;
   memo[estado] = calcular estado atual
   return memo[estado];
}

Complexidade

• De modo geral, a complexidade da DP é calculada da seguinte forma:

  • $O(\text{|Estados|} \cdot \text{|Transição por estado|)}$
  • Por exemplo, o seguinte código:

  int fib(int n) {
     if (n <= 1) return n;
     if (memo[n] == -1)
  	   memo[n] = fib(n-1) + fib(n-2);
     return memo[n];
  }
  

  • Possui $O(n)$ estados e cada estado é processado em $O(1)$. Dessa forma, a complexidade é $O(n)$.