Алгоритмы с нуля
Табуляция: восходящее ДП, таблица
В прошлом уроке мемоизация вычисляла каждую подзадачу Фибоначчи один раз, кэшируя рекурсию. Это работает, но всё ещё рекурсирует: fib(n) спускается вызовами до fib(0) прежде чем хоть что-то вернётся, и эта цепочка незавершённых вызовов это стек который может стать достаточно глубоким чтобы рухнуть. Теперь переверни всё с ног на голову. Вместо того чтобы начать от цели и рекурсировать вниз, начни от базовых случаев и строй вверх. Разложи ряд коробок — одна на подзадачу. Запиши два ответа которые ты уже знаешь, fib(0) и fib(1). Потом пройди ряд слева направо обычным циклом, заполняя каждую коробку из двух предыдущих. Без рекурсии, без стека, и когда ты дойдёшь до последней коробки у тебя есть ответ. Это табуляция: восходящее ДП, таблица.
После этого урока ты можешь реализовать динамическое программирование снизу вверх с табуляцией. Ты можешь назвать четыре части которые нужны каждому табулированному ДП: массив dp и что значит каждая его ячейка, базовые случаи которые его засевают, переход (рекуррента в форме массива), и порядок обхода который гарантирует что каждая ячейка заполнена прежде чем что-либо её читает. Ты можешь преобразовать мемоизированное (нисходящее) решение в табулированное (восходящее) и для Фибоначчи, и для подъёма по лестнице. Ты можешь противопоставить два направления: табуляция не платит за стек рекурсии и работает в предсказуемом порядке, но она вычисляет каждое состояние даже те которые нисходящий запуск пропустил бы; мемоизация вычисляет только достижимые состояния но платит за стек и хеширование. Ты можешь применить оптимизацию памяти: когда ячейка зависит только от последних нескольких ячеек, держи только их в скользящем окне и выбрось всю таблицу, уменьшив память Фибоначчи с O(n) до O(1). Это закрывает основы ДП; более поздние уроки применяют таблицу к более сложным рекуррентам.
Что это табуляция?
Табуляция это восходящий способ писать динамическое программирование. Вместо рекурсии что начинает от цели и спускается к базовым случаям, ты создаёшь таблицу — обычно массив называемый dp — заполняешь базовые случаи напрямую, потом запускаешь цикл который заполняет остаток таблицы в порядке где каждая ячейка которую ты вычисляешь читает только ячейки которые уже заполнены. Когда цикл заканчивается, ответ сидит в ячейке для цели. Нет рекурсии и нет стека вызовов.
Четыре части каждого табулированного ДП
Табулированное решение это всегда те же четыре решения. Сделай их правильно и код пишется сам:
- Массив dp и его значение. Реши что
dp[i]обозначает. Для Фибоначчиdp[i]это “i-е число Фибоначчи”. Записать это значение одним предложением это самый важный шаг — всё остальное следует из него. - Базовые случаи. Ячейки которые ты можешь заполнить без вычислений. Для Фибоначчи:
dp[0] = 0иdp[1] = 1. - Переход (рекуррента). Как вычислить небазовую ячейку из более ранних ячеек. Для Фибоначчи:
dp[i] = dp[i - 1] + dp[i - 2]. Это ровно та же рекуррента что использовала рекурсия, только читающая массив вместо совершения вызовов. - Порядок обхода. Порядок заполнения ячеек так чтобы когда ты вычисляешь
dp[i], каждая ячейка от которой она зависит уже готова. Для Фибоначчиdp[i]нуждается вdp[i-1]иdp[i-2], так что заполнение слева направо (i от 2 до n) гарантирует что обе готовы.
Почему порядок обхода это весь фокус
Мемоизация никогда не беспокоилась о порядке — рекурсия обнаруживала порядок по запросу. У табуляции нет рекурсии чтобы что-либо обнаруживать, так что ты должен выбрать порядок который уважает зависимости. Правило простое: ячейка может зависеть только от ячеек заполненных раньше в цикле. Для Фибоначчи зависимость указывает назад (i нуждается в i-1 и i-2), так что движение вперёд от базовых случаев её удовлетворяет. Если бы ты ошибся с порядком — скажем попробовал заполнить dp[i] прежде чем dp[i-1] существовала — ты прочитал бы пустую ячейку и получил мусор.
Табуляция как та же рекуррента, запущенная вперёд
Мемоизация и табуляция решают идентичную рекуррену с идентичными базовыми случаями. Единственная разница это направление:
memoization (top-down): start at fib(n), recurse DOWN to fib(0), fill cache on the way back up
tabulation (bottom-up): start at fib(0), loop UP to fib(n), fill the table left to rightСмотри как таблица заполняется, слева направо
Для fib dp начинается с двух базовых случаев, и каждый шаг добавляет сумму двух ячеек слева от него. ”?” отмечает ячейки ещё не вычисленные:
seed bases: dp = [0, 1, ?, ?, ?, ?, ?, ?]
i = 2: dp[2] = dp[1] + dp[0] = 1 -> [0, 1, 1, ?, ?, ?, ?, ?]
i = 3: dp[3] = dp[2] + dp[1] = 2 -> [0, 1, 1, 2, ?, ?, ?, ?]
i = 4: dp[4] = dp[3] + dp[2] = 3 -> [0, 1, 1, 2, 3, ?, ?, ?]
i = 5: dp[5] = dp[4] + dp[3] = 5 -> [0, 1, 1, 2, 3, 5, ?, ?]
i = 6: dp[6] = dp[5] + dp[4] = 8 -> [0, 1, 1, 2, 3, 5, 8, ?]
i = 7: dp[7] = dp[6] + dp[5] = 13 -> [0, 1, 1, 2, 3, 5, 8, 13]
answer: dp[7] = 13Каждая ячейка вычисляется ровно раз, в одном чистом проходе слева направо. Ни одна ячейка никогда не читается прежде чем записана, потому что порядок цикла совпадает с направлением зависимости.
Цена движения снизу вверх
Табуляция вычисляет каждую ячейку от базовых случаев до цели, нужна она нисходящему запуску или нет. Для плотной задачи как Фибоначчи это не потеря — каждая ячейка всё равно нужна. Но если бы достижимые состояния были редкими (вообрази рекурсию которая когда-либо касается лишь разбросанной горстки возможных состояний), мемоизация вычислила бы только их, тогда как табуляция заполнила бы весь диапазон. Это компромисс который ты принимаешь в обмен на избавление от стека рекурсии.
Табулированный Фибоначчи (снизу вверх)
Это та же рекуррента и базовые случаи что и в мемоизированной версии из урока 02, но управляемая циклом по массиву вместо рекурсии по кэшу.
1
function fib(n) {
2
// Base cases handled directly
3
if (n <= 1) {
4
return n;
5
}
6
// dp[i] means "the i-th Fibonacci number"
7
const dp = new Array(n + 1);
8
dp[0] = 0; // base case
9
dp[1] = 1; // base case
10
// Fill left to right: every cell reads two already-filled cells
11
for (let i = 2; i <= n; i++) {
12
dp[i] = dp[i - 1] + dp[i - 2]; // the transition (recurrence)
13
}
14
// The goal is the last cell
15
return dp[n];
16
}
- L3 Охрани крошечные входы так чтобы dp[1] всегда был валидным индексом когда мы строим массив.
- L7 Массив dp: одна ячейка на подзадачу, индексы 0..n. dp[i] = i-е число Фибоначчи.
- L8 Базовый случай dp[0] = 0, заполнен без вычислений.
- L9 Базовый случай dp[1] = 1, заполнен без вычислений.
- L11 Порядок обхода: i идёт от 2 до n, так что dp[i-1] и dp[i-2] всегда уже заполнены.
- L12 Переход: каждая ячейка это сумма двух ячеек слева от неё. Та же рекуррента что у рекурсии, читающая массив.
- L15 После цикла dp[n] держит ответ. Без рекурсии, без стека.
Ключевой момент: нет стека рекурсии
Вся функция это один цикл. Ничто не вызывает само себя, так что нет цепочки незавершённых вызовов и нет стека вызовов чтобы расти. Для очень большого n мемоизированная версия могла переполнить стек на своём первом глубоком спуске; табулированная версия никогда не может — она просто итерирует.
Запуск: заполненная таблица и ответы
Напечатанная таблица это ровно тот ряд который мы заполнили вручную. Цикл сделал тот же проход слева направо.
Оптимизация памяти: скользящее окно
Посмотри на переход снова: dp[i] = dp[i - 1] + dp[i - 2]. Чтобы вычислить любую ячейку, тебе когда-либо нужны только последние две ячейки. Как только dp[i] вычислена, dp[i - 2] больше никогда не читается. Так что хранить весь массив расточительно — ты можешь держать только два последних значения в двух переменных и сдвигать их вперёд. Это скользящее окно уменьшает память Фибоначчи с O(n) до O(1) сохраняя то же O(n) время.
1
function fib(n) {
2
if (n <= 1) {
3
return n;
4
}
5
// Keep only the two cells the transition needs
6
let prev2 = 0; // plays the role of dp[i - 2], starts at fib(0)
7
let prev1 = 1; // plays the role of dp[i - 1], starts at fib(1)
8
for (let i = 2; i <= n; i++) {
9
const curr = prev1 + prev2; // the same transition, on the two kept values
10
prev2 = prev1; // slide the window forward
11
prev1 = curr;
12
}
13
return prev1; // prev1 now holds fib(n)
14
}
- L6 prev2 держит fib(i-2). Он начинается как fib(0) = 0.
- L7 prev1 держит fib(i-1). Он начинается как fib(1) = 1.
- L9 Тот же переход что в версии с массивом, но читающий две хранимые переменные.
- L10 Сдвинь окно: старый prev1 становится новым prev2.
- L11 А свежевычисленное значение становится новым prev1.
- L13 После цикла prev1 это fib(n). Мы никогда не хранили всю таблицу: O(1) память.
Те же ответы, один константный кусок памяти. Оптимизация памяти работает всякий раз когда переход дотягивается назад только на фиксированное число ячеек.
Второй пример: подъём по лестнице, табулированный
Рекуррента подъёма по лестнице из урока 02 это ways(n) = ways(n-1) + ways(n-2) — той же формы что Фибоначчи, с базовыми случаями ways(1) = 1 и ways(2) = 2. Так что версия с таблицей это та же механика: массив dp, две базовые ячейки, переход, цикл слева направо. И поскольку переход снова дотягивается назад только на две ячейки, оптимизация скользящего окна применяется ровно как для fib.
Обе версии согласны. Как только ты можешь назвать четыре части — массив, базовые случаи, переход, порядок — преобразование любого мемоизированного ДП в таблицу механично, а сжатие памяти это вопрос того насколько далеко назад дотягивается переход.
Давай протрассируем табулированный fib для n = 5 и посмотрим как ячейки заполняются слева направо. Массив dp начинается только с записанными базовыми случаями; каждый кадр вычисляет ещё одну ячейку из двух слева от неё. ”?” отмечает ячейку ещё не заполненную.
1
function fib(n) {
2
if (n <= 1) return n;
3
const dp = new Array(n + 1);
4
dp[0] = 0;
5
dp[1] = 1;
6
for (let i = 2; i <= n; i++) {
7
dp[i] = dp[i - 1] + dp[i - 2];
8
}
9
return dp[n];
10
}
Время: O(n)
Цикл запускается раз на ячейку от i = 2 до i = n, и каждая итерация делает O(1) работы (одно сложение, одно присваивание). Это n − 1 итераций константной работы, так что O(n). Это в точности совпадает с мемоизацией, и по той же причине: общее правило ДП это
total time = (number of distinct states) x (work per state)Для Фибоначчи это (n+1) состояний x O(1) работы = O(n), достигаешь ли ты состояний рекурсируя вниз или зацикливаясь вверх.
Память: O(n) с полной таблицей, O(1) со скользящим окном
Наивная табуляция хранит одну ячейку на состояние в массиве dp: O(n). Но стек рекурсии за который платила мемоизация исчез — у цикла нет глубины вызовов — так что память табуляции это просто таблица, без дополнительного O(n) слагаемого за стек.
Ещё лучше: переход dp[i] = dp[i-1] + dp[i-2] дотягивается назад только на две ячейки, так что тебе никогда не нужен весь массив сразу. Держи два последних значения в двух переменных и память падает до O(1) тогда как время остаётся O(n). Это оптимизация скользящего окна, и она применяется к любому ДП чей переход зависит только от фиксированного числа недавних состояний.
time space (table) space (rolling) stack
memoization O(n) O(n) cache — O(n) <- last lesson
tabulation O(n) O(n) table O(1) none <- this lessonКогда табуляция выигрывает, и когда нет
Преимущества табуляции это отсутствие стоимости стека рекурсии (так нет риска переполнения стека для огромного n), предсказуемый фиксированный порядок обхода, и лёгкий путь к O(1) памяти когда переход дотягивается назад лишь немного. Её цена в том что она вычисляет каждую ячейку от базовых случаев до цели, даже ячейки которые нисходящий запуск пропустил бы. Для плотных задач как fib это ничего не стоит — каждая ячейка нужна. Для редких, разбросанных пространств состояний “вычисляй только то чего достигаешь” мемоизации может сделать строго меньше работы. Выбери направление которое подходит задаче; рекуррента и O(n) время те же в любом случае.
Что это определяющая черта табуляции по сравнению с мемоизацией?
В табулированном ДП, почему порядок обхода имеет значение?
Для табулированного Фибоначчи, что это переход который заполняет небазовую ячейку dp[i]?
Почему табуляция Фибоначчи может быть оптимизирована с O(n) памяти до O(1) памяти?
Какую стоимость табуляция избегает которую платит нисходящая мемоизация?
Что это один недостаток табуляции по сравнению с мемоизацией?
Табулированное ДП имеет 250 различных состояний и делает O(1) работы на состояние. Примерно сколько вычислений ячеек цикл выполняет всего?
Почему это работает
Зачем учить табуляцию если мемоизация уже работает? Три причины. Первая, нет стека рекурсии: для очень большого n нисходящий запуск может переполнить стек вызовов, тогда как цикл никогда не может. Вторая, предсказуемость: фиксированный порядок обхода легко осмыслить и у него нет накладных расходов на вызов функции, так что он обычно немного быстрее на практике. Третья, и самая ценная, таблица делает оптимизацию памяти очевидной — как только ты видишь что переход дотягивается назад лишь на пару ячеек, скользящее окно которое роняет O(n) до O(1) почти пишет себя само. Частый рабочий поток это написать рекурсию, мемоизировать её чтобы получить корректное O(n) решение, потом табулировать когда тебе нужен меньший стек или меньшая память.
Частая ошибка
Ошибка: заполнение таблицы в порядке который читает пустые ячейки. У табуляции нет рекурсии чтобы обнаружить порядок, так что неверное направление цикла читает ячейки которые ещё не записаны. Если бы ты попробовал вычислить dp[i] прежде чем dp[i-1] существовала, ты прочитал бы undefined и произвёл NaN. Всегда проверяй направление зависимости сначала: dp[i] Фибоначчи зависит от меньших индексов, так что цикл должен идти вперёд от базовых случаев. Некоторые ДП зависят от больших индексов и должны зацикливаться назад. Подгони цикл под зависимости.
Граничные случаи
Крошечные входы и базовые случаи. Охрани малые входы прежде чем строить массив. Для Фибоначчи if (n <= 1) return n; обрабатывает n = 0 и n = 1, так что запись dp[1] = 1 никогда не индекс вне диапазона. Для подъёма по лестнице if (n <= 2) return n; покрывает две базовые ячейки. Пропуск этих охран это классический баг на единицу: построение массива длины n+1 а потом предположение что dp[1] существует когда n это 0 пишет за пределы массива из одного элемента.
Ещё практика
Рецепт для любого табулированного ДП. (1) Определи dp[i] одним предложением — что значит ячейка? (2) Заполни базовые случаи напрямую, без вычислений. (3) Напиши переход: как небазовая ячейка строится из более ранних ячеек (это та же рекуррента что использовала рекурсия). (4) Выбери порядок обхода так чтобы каждая ячейка была заполнена прежде чем она прочитана — вперёд когда зависимости указывают на меньшие индексы. (5) Спроси насколько далеко назад дотягивается переход; если лишь на фиксированную горстку ячеек, замени массив скользящими переменными для O(1) памяти. Попробуй рецепт на подъёме по лестнице выше, потом на подъёме по лестнице с минимальной стоимостью.
Объясни что это табуляция, четыре части которые ей нужны, почему порядок обхода имеет значение, как она сравнивается с мемоизацией, и как работает оптимизация скользящего окна.
Табуляция это восходящий способ писать динамическое программирование: построй массив dp, заполни базовые случаи, потом зацикливайся от малых состояний к цели. Без рекурсии, без стека вызовов.
Четыре части:
- Массив dp и его значение — реши одним предложением что
dp[i]обозначает (для fib, “i-е число Фибоначчи”). - Базовые случаи — ячейки которые ты заполняешь без вычислений (
dp[0] = 0,dp[1] = 1). - Переход (рекуррента) — как небазовая ячейка строится из более ранних ячеек (
dp[i] = dp[i-1] + dp[i-2]). - Порядок обхода — заполняй ячейки так чтобы каждая ячейка была вычислена прежде чем что-либо её читает. Вперёд когда зависимости указывают на меньшие индексы.
Снизу вверх против сверху вниз: табуляция зацикливается вверх от базовых случаев; мемоизация рекурсирует вниз от цели. Та же рекуррента, то же O(n) время. Табуляция не платит за стек рекурсии (нет переполнения для большого n) но вычисляет каждое состояние в диапазоне, даже те которые нисходящий запуск пропустил бы.
Оптимизация памяти (скользящее окно): когда переход дотягивается назад только на фиксированное число ячеек, держи только их в переменных и выбрось таблицу. Для Фибоначчи это уменьшает память с O(n) до O(1) с тем же O(n) временем.
Это закрывает основы ДП: задача, рекуррента, кэш или таблица. Мемоизируй когда достижимо лишь редкое множество состояний или порядок трудно спланировать; табулируй, когда нужны отсутствие стека, предсказуемый порядок или O(1) память.