DP: монеты, рюкзак и LIS

Три эталонные задачи DP, которые спрашивают чаще всего.

Состояние DP — описание подзадачи (например, «минимум монет на сумму k»), а переход — формула, связывающая его с меньшими подзадачами.

Размен монетами

Дан набор номиналов и сумма. Найти минимальное число монет, чтобы её набрать (или -1). Состояние: dp[s] — минимум монет на сумму s. Переход: пробуем каждую монету c и берём dp[s - c] + 1.

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for s in range(1, amount + 1):
        for c in coins:
            if c <= s:
                dp[s] = min(dp[s], dp[s - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 2, 5], 11))
print(coin_change([2], 3))
print(coin_change([1, 5, 10, 25], 30))

Вывод:

3
-1
2

Рюкзак 0/1

Есть предметы с весом и ценностью и рюкзак вместимости W. Каждый предмет берём целиком или не берём. Максимизировать ценность. Состояние: dp[w] — максимум ценности при вместимости w. Чтобы не использовать предмет дважды, внутренний цикл по весу идёт в обратном порядке.

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

print(knapsack([1, 3, 4], [15, 20, 30], 4))
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 5))

Вывод:

35
7

Наибольшая возрастающая подпоследовательность (LIS)

Найти длину самой длинной строго возрастающей подпоследовательности. Простой DP — O(n^2): dp[i] = длина LIS, заканчивающейся на i.

def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))
print(length_of_lis([0, 1, 0, 3, 2, 3]))

Вывод:

4
4

Как работает под капотом

Везде сначала формулируем состояние, потом переход и базу. В рюкзаке 0/1 обратный порядок внутреннего цикла критичен: при прямом порядке dp[w - weight] уже учёл бы текущий предмет, и он попал бы в рюкзак несколько раз (это была бы задача о неограниченном рюкзаке). В размене монетами порядок прямой именно потому, что монеты можно брать многократно.

Частые ошибки

• Перепутать направление цикла в рюкзаке 0/1 (обратный) и в размене монет (прямой).
• Забыть инициализировать dp[0] базовым случаем (0 монет на сумму 0).
• В LIS брать nums[j] <= nums[i] вместо строгого < — получите неубывающую, а не строго возрастающую.

Итог

• Алгоритм DP: определи состояние, переход и базу.
• Рюкзак 0/1 — обратный внутренний цикл (предмет один раз); монеты — прямой (многократно).
• LIS за O(n^2) через dp[i] = длина возрастающей подпоследовательности до i.