Чем мемоизация отличается от табуляции в динамическом программировании?

Мемоизация — это ДП сверху вниз: рекурсия плюс кеш уже посчитанных подзадач; табуляция — ДП снизу вверх: итеративное заполнение таблицы от базовых случаев к ответу.

Сравнение подходов

• Top-down (memo): пишется естественно из рекуррентной формулы, считает только реально нужные подзадачи, но платит стеком и накладными расходами на вызовы.
• Bottom-up (tabulation): без рекурсии, обычно быстрее по константам, проще оптимизировать память — например, хранить два последних значения вместо всей таблицы.

Пример: числа Фибоначчи

const memo = new Map();
const fib = (n) => {
  if (n < 2) return n;
  if (!memo.has(n)) memo.set(n, fib(n - 1) + fib(n - 2));
  return memo.get(n);
};

Табуляция: массив f, заполняемый в цикле от f[0] и f[1]. Обе версии — O(n) вместо экспоненциального перебора.

Коротко для собеседования

Мемоизация — рекурсия с кешем, которая считает только нужные подзадачи, табуляция — цикл, заполняющий таблицу от базовых случаев. Табуляция быстрее по константам и не упирается в стек; сама ДП применима, когда есть оптимальная подструктура и перекрывающиеся подзадачи.