House Robber, Coin Change, Word Break, Decode Ways.
Одномерное динамическое программирование. House Robber, Coin Change, Word Break.
Условие: Верните максимальную сумму, которую можно украсть, не ограбив два соседних дома.
Примеры:
Ввод: nums = [1,2,3,1]
Вывод: 4
Ввод: nums = [2,7,9,3,1]
Вывод: 12
Решение:
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev1, prev2 = 0, 0
for num in nums:
current = max(prev1, prev2 + num)
prev2, prev1 = prev1, current
return prev1Объяснение:
Сложность: O(n)
Условие: Дома расположены по кругу (первый и последний соседние).
Решение:
def rob(nums):
def rob_linear(houses):
prev1, prev2 = 0, 0
for num in houses:
prev1, prev2 = max(prev1, prev2 + num), prev1
return prev1
if len(nums) == 1:
return nums[0]
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))Объяснение:
Сложность: O(n)
Условие:
Верните минимальное количество монет для суммы amount или -1, если невозможно.
Решение:
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1Сложность: O(amount × len(coins))
Условие: Можно ли разбить строку на слова из словаря?
Решение:
def wordBreak(s, wordDict):
wordSet = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in wordSet:
dp[i] = True
break
return dp[len(s)]Сложность: O(n² × m)
Условие: Верните количество способов декодирования строки цифр в буквы (A=1, B=2, ..., Z=26).
Решение:
def numDecodings(s):
if not s or s[0] == '0':
return 0
dp = [0] * (len(s) + 1)
dp[0], dp[1] = 1, 1
for i in range(2, len(s) + 1):
if s[i-1] != '0':
dp[i] += dp[i-1]
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[len(s)]Сложность: O(n)
| Задача | Формула |
|---|---|
| House Robber | max(prev1, prev2 + num) |
| Coin Change | min(dp[i], dp[i-coin] + 1) |
| Word Break | dp[j] and s[j:i] in dict |
| Decode Ways | dp[i-1] + dp[i-2] |
# ❌ Неправильно
dp = [0] * (amount + 1) # Все 0!
# ✅ Правильно
dp[0] = 0, остальные = inf# ❌ Неправильно
# Нет проверки s[0] == '0'
# ✅ Правильно
if not s or s[0] == '0':
return 0Dynamic Programming: 1D — задачи с одним измерением.
Ключевые приёмы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.