Динамическое программирование

↑ 8.5 Алгоритмы и структуры данных на C♯ · ← Предыдущая · → Следующая

Желательно~3 мин чтенияУровень: senior

Зачем это на собесе

Задачи ДП встречаются на сложных этапах: важно уметь описать состояние и переход.

Объяснение

ДП применимо, когда задача разбивается на перекрывающиеся подзадачи с оптимальной подструктурой. Метод: описать состояние dp[i], переход, базу, порядок вычисления.

Подход	Суть
Сверху вниз (мемоизация)	рекурсия + кэш результатов
Снизу вверх (табуляция)	заполнение таблицы от базы
Оптимизация памяти	хранить только нужные предыдущие строки

// Числа Фибоначчи: O(n) времени, O(1) памяти
static long Fib(int n) { long a = 0, b = 1; for (int i = 0; i < n; i++) (a, b) = (b, a + b); return a; }
 
// Монеты: минимум монет для суммы amount
static int CoinChange(int[] coins, int amount)
{
    var dp = new int[amount + 1]; Array.Fill(dp, int.MaxValue); dp[0] = 0;
    for (int s = 1; s <= amount; s++)
        foreach (var c in coins)
            if (c <= s && dp[s - c] != int.MaxValue) dp[s] = Math.Min(dp[s], dp[s - c] + 1);
    return dp[amount] == int.MaxValue ? -1 : dp[amount];
}
 
// Наибольшая общая подпоследовательность (LCS)
static int Lcs(string a, string b)
{
    var dp = new int[a.Length + 1, b.Length + 1];
    for (int i = 1; i <= a.Length; i++)
        for (int j = 1; j <= b.Length; j++)
            dp[i, j] = a[i - 1] == b[j - 1] ? dp[i - 1, j - 1] + 1 : Math.Max(dp[i - 1, j], dp[i, j - 1]);
    return dp[a.Length, b.Length];
}

Классические задачи: ступеньки (climbing stairs), рюкзак 0/1, наибольшая возрастающая подпоследовательность (LIS), расстояние Левенштейна, подмножество с заданной суммой, декодирование строки, House Robber.

Как подходить на интервью: (1) полный перебор рекурсией; (2) найти повторяющиеся подзадачи; (3) добавить мемоизацию; (4) при необходимости перейти к таблице и сократить память.

Нюансы и подводные камни

• Неверное определение состояния — источник ошибок; формулируйте словами, что означает dp[i][j].
• Инициализация int.MaxValue + 1 → переполнение.
• Глубокая рекурсия с мемоизацией — StackOverflow; табуляция безопаснее.
• Жадный алгоритм не всегда даёт оптимум (монеты нестандартных номиналов) — нужен ДП.

Практика

1. Решите: Climbing Stairs, House Robber, Coin Change, LIS, Edit Distance.
2. Сократите память для LCS до двух строк.
3. Опишите состояние и переход для рюкзака 0/1 словами.

Вопросы с ответами

Когда применять динамическое программирование?

Когда есть перекрывающиеся подзадачи и оптимальная подструктура, а перебор экспоненциален.

Мемоизация или табуляция?

Мемоизация проще писать и считает только нужные состояния; табуляция избегает рекурсии и позволяет экономить память.

Связанные темы

• Сортировка, бинарный поиск, PriorityQueue
• [[be-8-5-7-tipovye-zadachi-layv-kodinga|Типовые задачи лайв-кодинга на C#]]