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

Задача о самой длинной общей подпоследовательности (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]

 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  
 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 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 
 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]  
 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 
 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]  
 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] 
 Заключение
 Динамическое программирование — это мощный инструмент, необходимый для решения множества сложных задач спортивного программирования. Алгоритмы, обсуждаемые в этом блоге, — лишь некоторые из многих проблем, которые можно решить с помощью динамического программирования. Освоив эти алгоритмы и поняв лежащие в их основе принципы, вы сможете стать более конкурентоспособным программистом и решать более сложные задачи.
 Материалы по теме
 Источники
 Источник
 
Читайте также:  Объектно ориентированным языком программирования является язык