23 · DP ПО НЕСКОЛЬКИМ ОСЯМ

Динамика: многомерная

Состояние зависит от двух координат: позиций в строках, клетки сетки или количества выбранных элементов.

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

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

Примитивы Go

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

Матрица DP

dp := make([][]int, rows+1)
for r := range dp {
    dp[r] = make([]int, cols+1)
}

Строки выделяются независимо.

Одна строка

for r := 1; r <= rows; r++ {
    for c := 1; c <= cols; c++ {
        dp[c] = combine(dp[c], dp[c-1])
    }
}

Порядок обновления критичен при сжатии памяти.

ПРАКТИКА

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

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

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

Уникальные пути

К клетке приходим сверху или слева.

O(rows · cols) time · O(cols) space

solution.go

func uniquePaths(rows, cols int) int {
    dp := make([]int, cols)
    dp[0] = 1
    for r := 0; r < rows; r++ {
        for c := 1; c < cols; c++ { dp[c] += dp[c-1] }
    }
    return dp[cols-1]
}

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

Наибольшая общая подпоследовательность

Совпали символы — диагональ + 1, иначе максимум соседей.

O(a · b) time · O(b) space

solution.go

func longestCommonSubsequence(a, b string) int {
    dp := make([]int, len(b)+1)
    for i := 1; i <= len(a); i++ {
        diagonal := 0
        for j := 1; j <= len(b); j++ {
            above := dp[j]
            if a[i-1] == b[j-1] { dp[j] = diagonal+1 } else { dp[j] = max(dp[j], dp[j-1]) }
            diagonal = above
        }
    }
    return dp[len(b)]
}

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

Минимальная сумма пути

Каждая клетка добавляется к лучшему пути сверху или слева.

O(rows · cols) time · O(cols) space

solution.go

func minPathSum(grid [][]int) int {
    dp := make([]int, len(grid[0]))
    for r := range grid {
        for c := range grid[r] {
            if r == 0 && c == 0 { dp[c] = grid[r][c]
            } else if r == 0 { dp[c] = dp[c-1]+grid[r][c]
            } else if c == 0 { dp[c] += grid[r][c]
            } else { dp[c] = min(dp[c], dp[c-1])+grid[r][c] }
        }
    }
    return dp[len(dp)-1]
}

ПЕРЕД КОДОМ

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

Что означают обе координаты
Нужна текущая или предыдущая строка
Проверь порядок циклов после оптимизации