Qual é a diferença entre programação dinâmica vs memorização vs tabulação?

Recursão com memorização (também conhecida como programação dinâmica de cima para baixo) e tabulação (também conhecida como programação dinâmica de baixo para cima) são as duas técnicas que compõem a programação dinâmica.

Algumas pessoas insistem que o termo “programação dinâmica” se refere apenas à tabulação e que a recursão com memorização é uma técnica diferente. É apenas uma questão de qual nome você atribui a ele. Pessoalmente, gosto do uso comum de me referir a ambas as técnicas sob o mesmo termo de “programação dinâmica”, considerando que a programação dinâmica de baixo para cima pode muito naturalmente ser vista como uma otimização da programação dinâmica de cima para baixo, que pode ser vista como um otimização (geralmente muito significativa) da recursão ingênua (não memorizada).

Bottom-up é uma otimização da técnica de cima para baixo e requer que você tenha mais informações sobre o problema. Requer que você especifique a fórmula de avaliação (também conhecida como recorrência) para a função, por exemplo, F (x) = F (x-1) + F (x-2), e também a ordem de avaliação para as diferentes chamadas para F, por exemplo comece a avaliar em x = 0 e aumente para cima. De cima para baixo localiza automaticamente a ordem de avaliação correta por meio de recursão e requer que você conheça apenas a fórmula de avaliação.

De baixo para cima pode ser mais eficiente em alguns casos, porque a recursão pode ser otimizada, economizando na sobrecarga de chamadas recursivas.