Dynamic Programming: 1D

Одномерное динамическое программирование. House Robber, Coin Change, Word Break.

#1. House Robber (LeetCode 198) 🟦 Medium

Ссылка: https://leetcode.com/problems/house-robber/

Условие: Верните максимальную сумму, которую можно украсть, не ограбив два соседних дома.

Примеры:

Ввод: 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

Объяснение:

prev1 — максимум до предыдущего дома
prev2 — максимум до дома перед предыдущим
current = max(prev1, prev2 + num)

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

#2. House Robber II (LeetCode 213) 🟦 Medium

Ссылка: https://leetcode.com/problems/house-robber-ii/

Условие: Дома расположены по кругу (первый и последний соседние).

Решение:

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)

#3. Coin Change (LeetCode 322) 🟦 Medium

Ссылка: https://leetcode.com/problems/coin-change/

Условие: Верните минимальное количество монет для суммы 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))

#4. Word Break (LeetCode 139) 🟦 Medium

Ссылка: https://leetcode.com/problems/word-break/

Условие: Можно ли разбить строку на слова из словаря?

Решение:

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)

#5. Decode Ways (LeetCode 91) 🟦 Medium

Ссылка: https://leetcode.com/problems/decode-ways/

Условие: Верните количество способов декодирования строки цифр в буквы (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)

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

Задача	Формула
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]

#7. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильная инициализация Coin Change

# ❌ Неправильно
dp = [0] * (amount + 1)  # Все 0!

# ✅ Правильно
dp[0] = 0, остальные = inf

#❌ Ошибка 2: Забыли проверку на '0' в Decode Ways

# ❌ Неправильно
# Нет проверки s[0] == '0'

# ✅ Правильно
if not s or s[0] == '0':
    return 0

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

Dynamic Programming: 1D — задачи с одним измерением.

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

House Robber: max из двух вариантов
Coin Change: inf инициализация
Word Break: dp[0] = True для пустой строки

Задача

Формула

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: 1D