Dynamic Programming: Продвинутые задачи

Longest Palindromic Substring, Burst Balloons, Regular Expression, Partition Equal Subset Sum.

#1. Longest Palindromic Substring (LeetCode 5) 🟦 Medium

Ссылка: https://leetcode.com/problems/longest-palindromic-substring/

Условие: Найдите самую длинную подстроку-палиндром.

Решение:

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

    # Длина 1
    for i in range(n):
        dp[i][i] = True

    # Длина 2
    for i in range(n - 1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start, max_len = i, 2

    # Длина 3 и более
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                start, max_len = i, length

    return s[start:start + max_len]

Сложность: O(n²)

#2. Burst Balloons (LeetCode 312) 🔴 Hard

Ссылка: https://leetcode.com/problems/burst-balloons/

Условие: Верните максимальное количество монет, которое можно получить, взрывая шары.

Решение:

def maxCoins(nums):
    nums = [1] + [x for x in nums if x > 0] + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for k in range(left + 1, right):
                coins = (nums[left] * nums[k] * nums[right] +
                        dp[left][k] + dp[k][right])
                dp[left][right] = max(dp[left][right], coins)

    return dp[0][n-1]

Объяснение:

Добавляем границы 1 в начало и конец
dp[left][right] — максимум для диапазона (left, right)
Перебираем последний взорванный шар k

Сложность: O(n³)

#3. Regular Expression Matching (LeetCode 10) 🔴 Hard

Ссылка: https://leetcode.com/problems/regular-expression-matching/

Условие: Реализуйте поддержку регулярных выражений с '.' и '*'.

Решение:

def isMatch(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    # Обработка '*' в начале
    for j in range(2, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-2]  # Ноль вхождений
                if p[j-2] == s[i-1] or p[j-2] == '.':
                    dp[i][j] = dp[i][j] or dp[i-1][j]  # Одно или более
            else:
                dp[i][j] = (p[j-1] == s[i-1] or p[j-1] == '.') and dp[i-1][j-1]

    return dp[m][n]

Сложность: O(m × n)

#4. Partition Equal Subset Sum (LeetCode 416) 🟦 Medium

Ссылка: https://leetcode.com/problems/partition-equal-subset-sum/

Условие: Верните true, если можно разбить массив на два подмножества с равной суммой.

Решение:

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False

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

    for num in nums:
        for i in range(target, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]

    return dp[target]

Сложность: O(n × sum)

#5. Шпаргалка

Задача	Ключевая идея
Longest Palindrome	dp[i][j] = s[i]==s[j] and dp[i+1][j-1]
Burst Balloons	Перебор последнего шара k
Regex Matching	'*' = ноль или более вхождений
Partition	0/1 Knapsack до target

#6. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильный порядок циклов в Partition

# ❌ Неправильно — прямой порядок
for i in range(num, target + 1):  # Можно использовать num многократно!

# ✅ Правильно — обратный порядок
for i in range(target, num - 1, -1):  # Каждый элемент один раз

#❌ Ошибка 2: Забыли проверку нечётной суммы

# ❌ Неправильно
# Нет проверки total % 2

# ✅ Правильно
if total % 2 != 0:
    return False

#7. Заключение

Dynamic Programming: Продвинутые задачи — сложные задачи с различными паттернами.

Ключевые приёмы:

Longest Palindrome: dp[i][j] для подстрок
Burst Balloons: перебор последнего элемента
Regex: обработка '*' — ноль или более
Partition: 0/1 Knapsack

Задача

Ключевая идея

Longest Palindrome

dp[i][j] = s[i]==s[j] and dp[i+1][j-1]

Burst Balloons

Перебор последнего шара k

Regex Matching

'*' = ноль или более вхождений

Partition

0/1 Knapsack до target

DP: Продвинутый