Python в задачах динамического программирования

Раздел: Python -> Алгоритмы

Основы динамического программирования

Динамическое программирование (ДП) - метод оптимизации, используемый для решения задач, которые могут быть разбиты на перекрывающиеся подзадачи. Вместо повторных вычислений ДП сохраняет результаты подзадач, что сокращает время выполнения. Рассмотрим два основных подхода: нисходящий (мемоизация) и восходящий (таблица).

Как вычислить число Фибоначчи без повторных вычислений?

Нисходящий подход с мемоизацией использует рекурсию и словарь для хранения уже вычисленных значений. Это интуитивно понятно и легко реализуемо.

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

алгоритмы и структуры данных python (алгоритмы и структуры данных в python)

Проблема: при больших n рекурсия может переполнить стек. Решение: увеличить лимит рекурсии или перейти к итеративному методу.

Как улучшить производительность и избежать рекурсии?

Восходящий подход (таблица) использует цикл и массив для последовательного вычисления значений.

def fibonacci_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

динамическое программирование python (решение задач динамического программирования на python)

Этот метод быстрее и не вызывает рекурсивных вызовов. Однако требует памяти O(n).

Почему простой рекурсивный метод Фибоначчи крайне медленный?

Из-за экспоненциального количества повторных вычислений. Для n=40 число вызовов превышает 300 миллионов. Проблема решается мемоизацией или итеративным способом.

Как сократить потребление памяти в восходящем подходе?

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

def fibonacci_opt(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a+b
    return b

типы алгоритмов в python (типы алгоритмов в python)

Память O(1), время O(n).

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

Как выбрать предметы с максимальной стоимостью при ограниченном весе?

Итеративное решение с таблицей – классический восходящий подход. Создаём матрицу dp, где dp[i][w] – максимальная стоимость для первых i предметов и веса w.

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

алгоритм выбора python (алгоритм выбора (selection) на python)

Время O(n*W), память O(n*W).

Как решить рюкзак рекурсивно с мемоизацией?

def knapsack_rec(i, w, memo, weights, values):
    if i == 0 or w == 0:
        return 0
    if (i, w) in memo:
        return memo[(i, w)]
    if weights[i-1] > w:
        result = knapsack_rec(i-1, w, memo, weights, values)
    else:
        result = max(knapsack_rec(i-1, w, memo, weights, values),
                     knapsack_rec(i-1, w-weights[i-1], memo, weights, values) + values[i-1])
    memo[(i, w)] = result
    return result

Этот вариант также правилен, но может быть медленнее из-за рекурсивных вызовов.

Какие ошибки часто допускают при решении рюкзака?

Неверное определение базового случая, путаница с индексами (0 vs 1), игнорирование ограничения веса, попытка использовать жадный алгоритм. Также необходимо следить за целочисленными типами, если веса большие.

- максимальная сумма python (максимальная сумма)

Дополнительные примеры с подробным разбором

Задача о наибольшей общей подпоследовательности (LCS)

Даны две строки, нужно найти длину их наибольшей общей подпоследовательности. Подпоследовательность может быть не непрерывной.

Пример

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs("ABCBDAB", "BDCAB"))  # Вывод: 4

Пояснение: таблица заполняется слева направо и сверху вниз. Если символы совпадают, прибавляем к диагональному значению 1. Иначе берём максимум из верхнего и левого соседа.

Задача о лестнице (количество способов подъёма)

Человек может подниматься на 1 или 2 ступеньки. Сколько способов достичь вершины из n ступенек?

Пример

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0]*(n+1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(climb_stairs(5))  # Вывод: 8

Объяснение: Чтобы попасть на i-ю ступеньку, нужно сначала быть на (i-1) или (i-2). Суммируем количество способов для этих состояний.

Задача о сумме подмножеств (Subset Sum)

Дан массив чисел и целевая сумма S. Определить, можно ли выбрать подмножество с суммой, равной S.

Пример

def subset_sum(nums, S):
    n = len(nums)
    dp = [[False]*(S+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = True
    for i in range(1, n+1):
        for s in range(1, S+1):
            if nums[i-1] <= s:
                dp[i][s] = dp[i-1][s] or dp[i-1][s - nums[i-1]]
            else:
                dp[i][s] = dp[i-1][s]
    return dp[n][S]

print(subset_sum([3, 34, 4, 12, 5, 2], 9))  # Вывод: True (4+5)

Пояснение: dp[i][s] истина, если сумму s можно составить из первых i элементов. Рекуррентное соотношение: либо не используем текущий элемент, либо используем, если его значение не превышает s.

Задача о разбиении строки (Word Break)

Дана строка и словарь слов, можно ли разбить строку на последовательность слов из словаря (слова могут повторяться)?

Пример

def word_break(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False]*(n+1)
    dp[0] = True
    for i in range(1, n+1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

print(word_break("leetcode", ["leet", "code"]))  # Вывод: True

Анализ: dp[i] означает, что префикс длины i может быть разбит. Перебираем все возможные последние слова s[j:i] и проверяем, разбиваем ли предыдущий префикс.

Оптимизация памяти для рюкзака 0/1

Вместо двумерной таблицы можно использовать одномерный массив, обновляя его справа налево, чтобы избежать повторного использования предмета:

Пример

def knapsack_1d(weights, values, W):
    n = len(weights)
    dp = [0]*(W+1)
    for i in range(n):
        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_1d([2,3,4,5], [3,4,5,6], 5))  # Вывод: 7

Пояснение: обратный проход гарантирует, что каждый предмет используется не более одного раза. Это экономит память O(W) вместо O(n*W).

Решение задач динамического программирования на Python - comments

динамическое программирование python (python)