DP снизу вверх с табуляцией
Преобразуйте решения сверху вниз в итеративные таблицы DP и сокращайте память с O(n) до O(1), когда нужны только несколько последних значений
«DP снизу вверх с табуляцией» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Восходящий DP: подход с табуляцией
Восходящий DP (табуляция) заполняет таблицу ответов для подзадач, начиная с самых маленьких подзадач и постепенно переходя к итоговому ответу. Вместо рекурсивного спуска и сохранения результатов при возврате вы вычисляете значения итеративно, снизу вверх. Обычно таблица представляет собой одномерный или двумерный массив, где каждая ячейка вычисляется на основе ранее заполненных ячеек. Это полностью устраняет рекурсию: не нужны стек вызовов и ограничение рекурсии, а локальность доступа к памяти улучшается.
# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)
# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')Восходящие числа Фибоначчи
Восходящий алгоритм для чисел Фибоначчи заполняет dp[0..n] слева направо. dp[i] = dp[i-1] + dp[i-2] для i >= 2. Базовые значения — dp[0] = 0 и dp[1] = 1 — записываются непосредственно в массив. Время работы составляет O(n), а сложность по памяти — O(n) для полной таблицы. Когда вы видите, что dp[i] зависит только от двух последних значений, можно сократить затраты памяти до O(1) с помощью двух переменных — это этап оптимизации памяти.
def fib_bottom_up(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0 # base case
dp[1] = 1 # base case
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# Space-optimised to O(1):
def fib_optimised(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fib_optimised(50)) # 12586269025Восходящий размен монет
Для задачи о размене монет восходящая таблица содержит значения dp[0..N], где dp[i] — минимальное число монет для получения суммы i. Инициализируйте dp[0] = 0 (ноль монет для нулевой суммы), а значения dp для сумм от 1 до N — бесконечностью. Для каждой суммы i от 1 до целевой попробуйте каждый номинал c: если i >= c, новое dp[i] равно минимуму из dp[i] и 1 + dp[i - c]. Ответ — значение dp для целевой суммы или -1, если оно по-прежнему равно бесконечности.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins for amount 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin: # can use this coin
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 5, 6, 9], 11)) # 2: (5+6)
print(coin_change([2], 3)) # -1: impossible
print(coin_change([1, 2, 5], 11)) # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249)) # 20Порядок заполнения: ключевая идея
Порядок заполнения — основа восходящего DP. Для любого состояния dp[i] все состояния, от которых оно зависит, должны быть вычислены заранее. В одномерном DP, где dp[i] зависит от dp[i-1] и dp[i-2], заполняйте таблицу слева направо. В двумерном DP, где dp[i][j] зависит от dp[i-1][j] и dp[i][j-1], заполняйте её построчно: сверху вниз и слева направо. Перед написанием кода всегда рисуйте стрелки зависимостей, чтобы подтвердить порядок заполнения.
# Fill order examples:
# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n
# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.
# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems
print('Draw dependencies first, then determine fill order')Восходящий LCS: двумерная таблица
Восходящая таблица для наибольшей общей подпоследовательности имеет размер (m+1) × (n+1), где dp[i][j] = LCS для s1[:i] и s2[:j]. Базовые случаи: dp[0][j] = dp[i][0] = 0 (пустая строка имеет LCS длины 0 с любой строкой). Заполняйте таблицу построчно: если s1[i-1] == s2[j-1], то dp[i][j] = 1 + dp[i-1][j-1]; иначе dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Ответ находится в dp[m][n].
def lcs_bottom_up(s1, s2):
m, n = len(s1), len(s2)
# (m+1) x (n+1) table, initialised to 0
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]: # characters match
dp[i][j] = 1 + dp[i-1][j-1]
else: # skip one character
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs_bottom_up('abcde', 'ace')) # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB')) # 4: 'BCAB' or 'BDAB'Оптимизация памяти: скользящий массив
Многие двумерные таблицы DP можно сократить до одномерной таблицы или двух строк, если заметить, что dp[i][j] зависит только от текущей и предыдущей строки. Храните два массива: prev и curr или обновляйте один массив в правильном порядке. Для LCS dp[i][j] зависит от dp[i-1][j], dp[i][j-1] и dp[i-1][j-1], поэтому достаточно хранить только предыдущую строку.
def lcs_space_optimised(s1, s2):
m, n = len(s1), len(s2)
# Keep only one row (previous row state)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = 1 + prev[j-1] # dp[i-1][j-1]
else:
curr[j] = max(prev[j], curr[j-1]) # dp[i-1][j] and dp[i][j-1]
prev = curr
return prev[n]
print(lcs_space_optimised('abcde', 'ace')) # 3
# Space: O(n) instead of O(mn)Восходящий DP для задачи о грабителе домов
Восходящий алгоритм для задачи о грабителе домов заполняет dp[0..n-1], где dp[i] — максимальная прибыль от ограбления домов с 0-го по i-й. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]), а для i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Поскольку dp[i] зависит только от двух последних значений, использование памяти сразу можно оптимизировать до O(1) с помощью двух переменных — это распространённая схема для одномерного DP с зависимостями через два шага.
def rob_bottom_up(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
# Full table version: O(n) space
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
def rob_optimised(nums):
# O(1) space: only need last two values
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12Минимальная сумма пути в таблице
Минимальная сумма пути (LeetCode #64): найдите путь из верхнего левого угла в нижний правый, минимизирующий сумму значений (можно двигаться только вправо или вниз). Двумерный DP: dp[i][j] = минимальная сумма для достижения ячейки (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Заполняйте таблицу слева направо и сверху вниз. Базовый случай: dp[0][0] = grid[0][0]; первую строку заполняйте только вправо, а первый столбец — только вниз.
def min_path_sum(grid):
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = grid[0][0]
# Fill first row (can only come from left)
for c in range(1, cols):
dp[0][c] = dp[0][c-1] + grid[0][c]
# Fill first column (can only come from above)
for r in range(1, rows):
dp[r][0] = dp[r-1][0] + grid[r][0]
# Fill rest of the table
for r in range(1, rows):
for c in range(1, cols):
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
return dp[rows-1][cols-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7: 1+3+1+1+1Изменение таблицы DP на месте
Когда дополнительная память запрещена, иногда можно изменить саму входную сетку и использовать её как таблицу DP. Для минимальной суммы пути перезапишите grid[i][j], указав в нём минимальную стоимость достижения этой ячейки. Это использует O(1) дополнительной памяти, но уничтожает входные данные — всегда сообщайте об этом компромиссе собеседнику и убедитесь, что такой подход допустим. Если входные данные необходимо сохранить, используйте метод скользящего массива.
def min_path_sum_inplace(grid):
rows, cols = len(grid), len(grid[0])
# Modify grid in-place (O(1) extra space, destroys input)
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
continue # starting cell
elif r == 0:
grid[r][c] += grid[r][c-1] # first row
elif c == 0:
grid[r][c] += grid[r-1][c] # first column
else:
grid[r][c] += min(grid[r-1][c], grid[r][c-1])
return grid[rows-1][cols-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Сравнение подходов сверху вниз и снизу вверх в задаче о размене монет
Оба подхода находят оптимальное решение задачи о размене монет, но на практике различаются. Подход сверху вниз проще записать, и он вычисляет только действительно достижимые подзадачи. Подход снизу вверх вычисляет все суммы от 0 до целевой, включая недостижимые с заданными монетами, которые так и остаются равными бесконечности. Для разреженных задач с небольшим количеством достижимых состояний подход сверху вниз эффективнее, а для плотных задач у подхода снизу вверх меньше накладных расходов.
import functools
# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0: return 0
if rem < 0: return float('inf')
return 1 + min(dp(rem - c) for c in coins)
r = dp(amount)
return r if r != float('inf') else -1
# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change_top([1,5,6,9], 11)) # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2Уникальные пути: классический двумерный DP
Уникальные пути (LeetCode № 62) — это задача на подсчёт количества путей из верхнего левого угла в нижний правый угол таблицы размера m×n, если двигаться можно только вправо или вниз. Рекуррентное соотношение просто: dp[i][j] = dp[i-1][j] + dp[i][j-1] — пути сверху плюс пути слева. Базовые случаи: вся первая строка и весь первый столбец содержат ровно по 1 пути, поскольку двигаться можно только в одном направлении. Этот двумерный DP заполняется за время O(mn), а занимаемую память можно уменьшить до O(n), используя скользящую строку.
def unique_paths(m, n):
# dp[i][j] = number of paths to reach cell (i,j)
dp = [[1] * n for _ in range(m)]
# Base: first row and first column are all 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 2)) # 3
# O(n) space rolling row:
def unique_paths_opt(m, n):
row = [1] * n
for _ in range(1, m):
for j in range(1, n):
row[j] += row[j-1]
return row[n-1]
print(unique_paths_opt(3, 7)) # 28Проверка знаний
Проверьте своё понимание концепций «Структуры данных & алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы изучили: DP снизу вверх с табулированием и определение порядка заполнения по стрелкам зависимостей, оптимизацию памяти с помощью скользящих массивов (от O(mn) до O(n)) и отслеживания двух переменных (от O(n) до O(1)), а также реализации снизу вверх для задач о числах Фибоначчи, размене монет, LCS, грабителе и минимальной сумме пути. Далее Вы решите задачи о размене монет и лестнице с минимальной стоимостью от начала до конца.
Часто задаваемые вопросы
Урок «DP снизу вверх с табуляцией» бесплатный?
Да — полный текст урока «DP снизу вверх с табуляцией» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «DP снизу вверх с табуляцией»?
Преобразуйте решения сверху вниз в итеративные таблицы DP и сокращайте память с O(n) до O(1), когда нужны только несколько последних значений Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «DP снизу вверх с табуляцией»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Распознавание DP: пересекающиеся подзадачи
- DP сверху вниз с мемоизацией
- DP снизу вверх с табуляцией
- Размен монет и подъём по лестнице с минимальной стоимостью