JackDaw 30 мая 2023

Python Алгоритмы

9973

🐍 25 алгоритмов динамического программирования, которые должен знать каждый программист

В этой статье мы рассмотрим 25 основных алгоритмов динамического программирования с реализацией на Python, которые должен знать каждый, кто увлекается спортивным программированием.

Данная статья является переводом. Автор: Rishita Shaw. Ссылка на оригинал.

Динамическое программирование — популярный метод в компьютерных науках и разработке программного обеспечения, который играет решающую роль в спортивном программировании. Это метод решения сложных проблем путем их разбиения на более мелкие подзадачи и решения каждой подзадачи только один раз с сохранением решений подзадач, чтобы их можно было повторно использовать при необходимости. В этой статье мы рассмотрим необходимые алгоритмы динамического программирования, которые должен знать каждый, кто увлекается спортивным программированием.

1. Числа Фибоначчи

Последовательность Фибоначчи — это хорошо известная последовательность чисел, определяемая рекуррентным соотношением F(n) = F(n-1) + F(n-2), где F(0) = 0 и F(1) = 1. Простым рекурсивным алгоритмом вычисления чисел Фибоначчи было бы прямое использование рекуррентного соотношения, но это привело бы к экспоненциальной временной сложности. Динамическое программирование позволяет решить эту задачу за линейное время с помощью мемоизации, которая сохраняет результаты уже решенных подзадач.

def fibonacci(n, memo):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

Статья по теме

⬇️🐍⬆️ Мемоизация vs bottom-up: какой подход динамического программирования требует меньше умственных усилий?

2. Самая длинная общая подпоследовательность

Задача о самой длинной общей подпоследовательности (LCS) — это классическая задача динамического программирования, которая включает в себя поиск самой длинной подпоследовательности, общей для двух заданных строк. Подпоследовательность строки — это последовательность символов, которые появляются в строке в одном и том же порядке, но не обязательно последовательно.

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    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]:
                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]

3. Задача о рюкзаке

Задача о рюкзаке — это классическая задача оптимизации, которая включает в себя поиск оптимального подмножества предметов для упаковки в рюкзак с конечной вместимостью, чтобы максимизировать ценность упакованных предметов.

def knapsack(W, wt, val, n):
    dp = [[0] * (W+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for w in range(1, W+1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]

Статья по теме

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

4. Расстояние Левенштейна (редакционное расстояние)

Задача редактирования расстояния заключается в нахождении минимального количества операций, необходимых для преобразования одной строки в другую. Допустимые операции: вставка, удаление и замена.

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]

    for i in range(m+1):
        for j in range(n+1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

    return dp[m][n]

5. Самый большой подмассив

Задача о самом большом подмассиве заключается в поиске непрерывного подмассива в одномерном массиве чисел с наибольшей суммой.

def max_subarray(arr):
    n = len(arr)
    max_sum = float('-inf')
    current_sum = 0

    for i in range(n):
        current_sum += arr[i]
        max_sum = max(max_sum, current_sum)
        current_sum = max(current_sum, 0)

    return max_sum

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека питониста»

Интересно, перейти к каналу

6. Размен монет

Проблема размена монет включает в себя поиск количества способов внести сдачу на заданную сумму денег, используя заданный набор номиналов монет.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount+1)
    dp[0] = 0

    for i in range(1, amount+1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i-coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

7. Умножение цепочки матриц

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

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[float('inf')] * n for _ in range(n)]
    s = [[0] * n for _ in range(n)]

    for i in range(n):
        m[i][i] = 0

    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            for k in range(i, j):
                q = m[i][k] + m[k+1][j] + p[i] * p[k+1] * p[j+1]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k

    return m, s

8. Самая длинная возрастающая подпоследовательность

Проблема самой длинной растущей подпоследовательности (LIS) включает в себя поиск самой длинной подпоследовательности заданной последовательности, которая строго возрастает. Проблема LIS имеет множество реальных приложений, таких как сжатие данных, распознавание образов и биоинформатика.

def lis(arr):
    n = len(arr)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

9. Задача коммивояжера

Задача коммивояжера (TSP) заключается в поиске кратчайшего возможного маршрута, который проходит через заданный набор городов и возвращается в начальный город. TSP — это классическая задача информатики, которая имеет множество реальных приложений, таких как логистика, транспорт и оптимизация сети.

def tsp(graph, start):
    n = len(graph)
    visited = (1 << n) - 1
    memo = {}

    def dfs(node, visited):
        if visited == 0:
            return graph[node][start]

        if (node, visited) in memo:
            return memo[(node, visited)]

        ans = float('inf')
        for i in range(n):
            if visited & (1 << i):
                ans = min(ans, graph[node][i] + dfs(i, visited ^ (1 << i)))

        memo[(node, visited)] = ans
        return ans

    return dfs(start, visited)

10. 0-1 Целочисленное программирование

Задача целочисленного программирования 0-1 включает в себя поиск оптимального решения для набора двоичных переменных решения с учетом набора ограничений. Задача целочисленного программирования 0-1 имеет множество практических применений, таких как распределение ресурсов, составление расписания и производственное планирование.

def knapsack(W, wt, val, n):
    dp = [[0] * (W+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for w in range(1, W+1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]

11. Расстояние Левенштейна с разрешенными операциями

Задача «Расстояние Левенштейна» может быть расширена, чтобы разрешить только определенный набор операций редактирования, таких как вставка, удаление и замена.

def edit_distance_with_allowed_ops(s1, s2, allowed_ops):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]

    for i in range(m+1):
        dp[i][0] = i

    for j in range(n+1):
        dp[0][j] = j

    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            elif allowed_ops.get((s1[i-1], s2[j-1])):
                op_cost = allowed_ops[(s1[i-1], s2[j-1])]
                dp[i][j] = min(dp[i-1][j] + op_cost[0], dp[i][j-1] + op_cost[1], dp[i-1][j-1] + op_cost[2])
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

    return dp[m][n]

12. Самая длинная палиндромная подстрока

Задача «Самая длинная палиндромная подстрока» заключается в поиске самой длинной подстроки заданной строки, которая является палиндромом.

def longest_palindromic_substring(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    max_len = 1
    start = 0

    for i in range(n):
        dp[i][i] = True

    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1

            if l == 2:
                dp[i][j] = s[i] == s[j]
            else:
                dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

            if dp[i][j] and l > max_len:
                max_len = l
                start = i

    return s[start:start+max_len]

13. Задача о подмассиве максимального произведения (Maximum Product Subarray)

Задача о подмассиве максимального произведения заключается в поиске непрерывного подмассива в одномерном массиве чисел с наибольшим произведением.

def max_product_subarray(nums):
    n = len(nums)
    max_prod = nums[0]
    min_prod = nums[0]
    max_so_far = nums[0]

    for i in range(1, n):
        temp = max_prod
        max_prod = max(nums[i], max(nums[i] * max_prod, nums[i] * min_prod))
        min_prod = min(nums[i], min(nums[i] * temp, nums[i] * min_prod))
        max_so_far = max(max_so_far, max_prod)

    return max_so_far

14. Самый большой прямоугольник на гистограмме

Задача «Самый большой прямоугольник в гистограмме» включает в себя поиск самого большого прямоугольника, который может быть сформирован на гистограмме, состоящей из прямоугольников разной высоты.

def largest_rectangle_area(heights):
    n = len(heights)
    left = [0] * n
    right = [0] * n
    stack = []

    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()

        left[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []
    for i in range(n-1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()

        right[i] = stack[-1] if stack else n
        stack.append(i)

    max_area = 0
    for i in range(n):
        max_area = max(max_area, heights[i] * (right[i] - left[i] - 1))

    return max_area

15. Бросание яиц

Задача о бросании яиц состоит в том, чтобы найти минимальное количество попыток, необходимых для определения самого высокого этажа, с которого яйцо может быть сброшено, не разбиваясь.

def egg_drop(n, k):
    dp = [[0] * (k+1) for _ in range(n+1)]

    for i in range(1, n+1):
        dp[i][1] = 1
        dp[i][0] = 0

    for j in range(1, k+1):
        dp[1][j] = j

    for i in range(2, n+1):
        for j in range(2, k+1):
            dp[i][j] = float('inf')
            for x in range(1, j+1):
                res = 1 + max(dp[i-1][x-1], dp[i][j-x])
                dp[i][j] = min(dp[i][j], res)

    return dp[n][k]

16. Подсчет битов

Задача подсчета битов заключается в том, чтобы найти количество единичных битов в двоичном представлении каждого числа от 0 до n.

def count_bits(n):
    dp = [0] * (n+1)

    for i in range(1, n+1):
        dp[i] = dp[i >> 1] + (i & 1)

    return dp

17. Идеальные квадраты

Задача о совершенных квадратах заключается в том, чтобы найти минимальное количество совершенных квадратных чисел, которые в сумме дают заданное число.

def num_squares(n):
    dp = [float('inf')] * (n+1)
    dp[0] = 0

    for i in range(1, n+1):
        j = 1
        while j*j <= i:
            dp[i] = min(dp[i], dp[i-j*j] + 1)
            j += 1

    return dp[n]

18. Раздел равной суммы подмножества (Partition Equal Subset Sum)

Проблема равной суммы подмножеств разделов включает в себя определение того, можно ли разбить данный набор на два подмножества так, чтобы сумма элементов в обоих подмножествах была одинаковой.

def can_partition(nums):
    n = len(nums)
    s = sum(nums)

    if s % 2 != 0:
        return False

    target = s // 2
    dp = [False] * (target+1)
    dp[0] = True

    for i in range(1, n+1):
        for j in range(target, nums[i-1]-1, -1):
            dp[j] |= dp[j-nums[i-1]]

    return dp[target]

19. Самая длинная общая подстрока

Задача «Самая длинная общая подстрока» заключается в поиске самой длинной подстроки, общей для двух заданных строк.

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    max_len = 0

    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                max_len = max(max_len, dp[i][j])

    return max_len

22. Уникальные пути

Проблема уникальных путей включает в себя поиск количества уникальных путей из верхнего левого угла в нижний правый угол сетки m x n, по которым вы можете двигаться только вниз или вправо.

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    for i in range(m):
        for j in range(n):
            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]

    return dp[m-1][n-1]

23. Расстояние Левенштейна с помощью разрешенных операций

Задачу «Расстояние Левенштейна» можно расширить, если мы хотим разрешить только определенный набор операций редактирования, таких как вставка, удаление и замена.

def edit_distance_with_allowed_ops(s1, s2, allowed_ops):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]

    for i in range(m+1):
        dp[i][0] = i

    for j in range(n+1):
        dp[0][j] = j

    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            elif allowed_ops.get((s1[i-1], s2[j-1])):
                op_cost = allowed_ops[(s1[i-1], s2[j-1])]
                dp[i][j] = min(dp[i-1][j] + op_cost[0], dp[i][j-1] + op_cost[1], dp[i-1][j-1] + op_cost[2])
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

    return dp[m][n]

24. Проблема суммы подмножества

Проблема суммы подмножества включает в себя определение того, существует ли подмножество заданного набора целых чисел, которое в сумме дает заданную сумму.

def subset_sum(nums, target):
    n = len(nums)
    dp = [[False] * (target+1) for _ in range(n+1)]

    for i in range(n+1):
        dp[i][0] = True

    for i in range(1, n+1):
        for j in range(1, target+1):
            if nums[i-1] <= j:
                dp[i][j] = dp[i-1][j-nums[i-1]] or dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][target]

25. Самая длинная палиндромная последовательность

Задача «Самая длинная палиндромная подпоследовательность» включает в себя поиск самой длинной подпоследовательности заданной строки, которая является палиндромом.

def longest_palindromic_substring(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    max_len = 1
    start = 0

    for i in range(n):
        dp[i][i] = True

    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1

            if l == 2:
                dp[i][j] = s[i] == s[j]
            else:
                dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

            if dp[i][j] and l > max_len:
                max_len = l
                start = i

    return s[start:start+max_len]

25. Самый большой прямоугольник на гистограмме

def largest_rectangle_area(heights):
    n = len(heights)
    left = [0] * n
    right = [0] * n
    stack = []

    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()

        left[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []
    for i in range(n-1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()

        right[i] = stack[-1] if stack else n
        stack.append(i)

    max_area = 0
    for i in range(n):
        max_area = max(max_area, heights[i] * (right[i] - left[i] - 1))

    return max_area

Уникальные пути 2

Задача «Уникальные пути II» — это разновидность задачи «Уникальные пути», в которой некоторые ячейки в сетке заблокированы и по ним нельзя пройти. Задача состоит в том, чтобы найти количество уникальных путей из верхнего левого угла в нижний правый угол сетки, где вы можете двигаться только вниз или вправо и не можете ходить по заблокированным ячейкам.

def unique_paths_with_obstacles(obstacle_grid):
    m, n = len(obstacle_grid), len(obstacle_grid[0])
    dp = [[0] * n for _ in range(m)]

    if obstacle_grid[0][0] == 0:
        dp[0][0] = 1

    for i in range(m):
        for j in range(n):
            if obstacle_grid[i][j] == 0:
                if i > 0:
                    dp[i][j] += dp[i-1][j]
                if j > 0:
                    dp[i][j] += dp[i][j-1]

    return dp[m-1][n-1]

Заключение

Динамическое программирование — это мощный инструмент, необходимый для решения множества сложных задач спортивного программирования. Алгоритмы, обсуждаемые в этом блоге, — лишь некоторые из многих проблем, которые можно решить с помощью динамического программирования. Освоив эти алгоритмы и поняв лежащие в их основе принципы, вы сможете стать более конкурентоспособным программистом и решать более сложные задачи.

***

Материалы по теме

Источники

https://dev.to/rishitashaw/dynamic-programming-algorithms-every-programmer-should-know-3915