Longest Palindrome, Burst Balloons, Regex, Partition.
Longest Palindromic Substring, Burst Balloons, Regular Expression, Partition Equal Subset Sum.
Условие: Найдите самую длинную подстроку-палиндром.
Решение:
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²)
Условие: Верните максимальное количество монет, которое можно получить, взрывая шары.
Решение:
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]Объяснение:
Сложность: O(n³)
Условие: Реализуйте поддержку регулярных выражений с '.' и '*'.
Решение:
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)
Условие:
Верните 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)
| Задача | Ключевая идея |
|---|---|
| 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 |
# ❌ Неправильно — прямой порядок
for i in range(num, target + 1): # Можно использовать num многократно!
# ✅ Правильно — обратный порядок
for i in range(target, num - 1, -1): # Каждый элемент один раз# ❌ Неправильно
# Нет проверки total % 2
# ✅ Правильно
if total % 2 != 0:
return FalseDynamic Programming: Продвинутые задачи — сложные задачи с различными паттернами.
Ключевые приёмы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.