Pular para o conteúdo

Top-down vs. bottom-up

Aula 2 de 20 · 5 min

Top-down vs. bottom-up

Passo 1 de 12

Top-down começa pelo problema completo, fib(4), e só desce na recursão até o que realmente precisa.

A ideia

Duas direções, uma recorrência. O top-down começa no problema completo, chama recursivamente e guarda em cache tudo o que encontra — então só toca os subproblemas de que realmente precisa. O bottom-up começa nos casos base e preenche uma tabela para a frente, então toda dependência está pronta antes de ser lida. O top-down sai mais fácil da recursão; o bottom-up evita uma pilha de chamadas (call stack) profunda.

Exemplo do mundo real

Revisar para uma prova. Top-down é abrir a prova antiga mais difícil e só consultar a matéria quando uma questão pede. Bottom-up é estudar o conteúdo programático capítulo por capítulo, para que nada falte quando você chegar à prova — mas você também estuda páginas que a prova nunca cobra.

O código

Sua vez

Coloque os passos em ordem.

  1. Preencha as células restantes na ordem de dependência
  2. Decida o que uma única célula da tabela vai significar
  3. Leia a célula final como a resposta
  4. Escreva diretamente as células dos casos base

Mini quiz

1 / 3

A DP top-down é mais bem descrita como: