DP на практике: лестница и задача о рюкзаке

Динамическое программирование на практике: задача о лестнице (варианты подъёма) и задача о рюкзаке (0/1 Knapsack) — формулировка подзадачи, переходы DP, таблица.

Ключ к динамическому программированию — сформулировать подзадачу: что нужно знать о подзадаче меньшего размера, чтобы решить исходную?

Задача о лестнице

За один шаг можно подняться на 1 или 2 ступеньки. Сколько способов добраться до N-й ступеньки?

Подзадача: ways[i] = количество способов добраться до ступеньки i.
Переход: ways[i] = ways[i-1] + ways[i-2] (пришли с предыдущей или с предпредыдущей).

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1   # 1 способ добраться до ступеньки 1
    dp[2] = 2   # 2 способа: (1+1) или (2)
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

for n in [3, 4, 5, 10]:
    print(f"Лестница {n} ступеней: {climb_stairs(n)} способов")

Вывод:

Лестница 3 ступеней: 3 способов
Лестница 4 ступеней: 5 способов
Лестница 5 ступеней: 8 способов
Лестница 10 ступеней: 89 способов

Замечаете? Это числа Фибоначчи! Задача о лестнице — та же структура переходов.

Задача о рюкзаке (0/1 Knapsack)

Есть рюкзак вместимостью W и набор предметов с весом и стоимостью. Нужно выбрать предметы, чтобы суммарная стоимость была максимальной, не превышая вместимость.

# Предметы: (вес, стоимость)
items = [(2, 3), (3, 4), (4, 5), (5, 6)]
W = 8   # вместимость рюкзака
n = len(items)

# dp[i][w] = максимальная стоимость при рассмотрении первых i предметов
#            и вместимости w
dp = [[0] * (W + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    weight, value = items[i - 1]
    for w in range(W + 1):
        # Не берём предмет i
        dp[i][w] = dp[i - 1][w]
        # Берём предмет i (если помещается)
        if w >= weight:
            take = dp[i - 1][w - weight] + value
            dp[i][w] = max(dp[i][w], take)

print(f"Максимальная стоимость: {dp[n][W]}")

# Восстанавливаем, какие предметы взяли
chosen = []
w = W
for i in range(n, 0, -1):
    if dp[i][w] != dp[i - 1][w]:
        chosen.append(i - 1)   # индекс предмета
        w -= items[i - 1][0]

print("Взятые предметы (индексы):", chosen[::-1])
print("Их вес и стоимость:", [(items[j][0], items[j][1]) for j in chosen[::-1]])

Вывод:

Максимальная стоимость: 10
Взятые предметы (индексы): [0, 1, 3]
Их вес и стоимость: [(2, 3), (3, 4), (5, 6)]

Идея таблицы dp

Сложность: O(n × W) по времени и памяти, где n — число предметов, W — вместимость. Это псевдополиномиальный алгоритм: зависит от числового значения W, а не его битового размера.

Коротко

• Задача о лестнице: ways[i] = ways[i-1] + ways[i-2] — та же структура, что Фибоначчи.
• Задача о рюкзаке: двумерная таблица dp[i][w], переход — взять или не взять предмет.
• Ключ DP: сформулировать подзадачу и переход, заполнить таблицу снизу вверх.
• Сложность рюкзака: O(n × W).