22 · ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Динамика: 1D

Определи значение dp[i], переход из меньших состояний и базовые случаи.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

DP-слайс

dp := make([]int, n+1)
dp[0] = base
for i := 1; i <= n; i++ { /* transition */ }

Сначала произнеси смысл dp[i] одним предложением.

Сжатие памяти

prev2, prev1 := base0, base1
current := combine(prev2, prev1)

Если нужны только последние состояния, слайс не требуется.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Домушник

Для каждого дома: пропустить или взять после i−2.

O(n) time · O(1) space

solution.go

func rob(nums []int) int {
    prev2, prev1 := 0, 0
    for _, money := range nums {
        prev2, prev1 = prev1, max(prev1, prev2+money)
    }
    return prev1
}

ПРИМЕР РЕШЕНИЯ

Размен монет

dp[sum] — минимум монет для этой суммы.

O(amount · coins) time · O(amount) space

solution.go

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for sum := 1; sum <= amount; sum++ {
        dp[sum] = amount+1
        for _, coin := range coins {
            if coin <= sum { dp[sum] = min(dp[sum], dp[sum-coin]+1) }
        }
    }
    if dp[amount] > amount { return -1 }
    return dp[amount]
}

ПРИМЕР РЕШЕНИЯ

Декодирование строки

Количество способов зависит от последних одной и двух цифр.

O(n) time · O(1) space

solution.go

func numDecodings(s string) int {
    prev2, prev1 := 1, 1
    for i := 1; i <= len(s); i++ {
        current := 0
        if s[i-1] != '0' { current += prev1 }
        if i > 1 && s[i-2:i] >= "10" && s[i-2:i] <= "26" { current += prev2 }
        prev2, prev1 = prev1, current
    }
    return prev1
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Что означает состояние
Какие базовые случаи
В каком порядке считать состояния