Табличный DP: снизу вверх

Снизу вверх (bottom-up)

Табличный DP — другой взгляд на ту же идею. Вместо рекурсииПриём, при котором функция вызывает саму себя. Нужен базовый случай, чтобы вызовы завершились. «сверху» мы идём снизу: заводим массив (таблицу) dp, заполняем самые простые случаи, а затем строим ответы посложнее из уже посчитанных. Никакой рекурсии и риска переполнить стек — только циклКонструкция, повторяющая блок кода: for перебирает элементы, while — пока условие истинно..

Часто всю таблицу хранить не нужно — для Фибоначчи достаточно двух последних значений. Это оптимизация по памяти с O(n) до O(1):

Классика: дом-грабитель (House Robber)

Задача с собеседований: дан списокИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. сумм денег в домах. Нельзя грабить два соседних дома. Какую максимальную сумму можно унести? Для каждого дома выбираем лучшее из двух: пропустить его (берём прошлый максимум) или ограбить (его деньги + максимум до позапрошлого).

Вернётся 20: грабим первый и последний дом (10 + 10), а средние пропускаем. ДП само находит этот выбор, перебирая на каждом шаге «брать или не брать».

⚠️ Частые ошибки новичков

Ошибка. Неправильно задать размер таблицы или базовые случаи — выйти за границы списка (IndexError) или забыть инициализировать dp[1]. Перед циклом всегда проверяйте маленькие n (0, 1) отдельно и убедитесь, что таблица длиной n + 1. Запустите код с ошибкой границ.