Динамическое программирование (1-D)

Динамическое программирование (1-D): как это работает?

Решите, что означает одно состояние. Обычно это лучший ответ по первым i элементам.

Запишите переход: как состояние i следует из более ранних. Этот переход и есть весь алгоритм.

Базовые случаи заполните вручную. Это состояния, под которыми нет ничего меньшего.

Идите вперёд и заполняйте таблицу по порядку. Всё, что она читает, уже посчитано.

Ответ лежит в одной ячейке, обычно в последней. Иногда это наибольшая ячейка таблицы.

Если переход смотрит только на два состояния назад, хватит двух переменных. Массив тогда не нужен.

1. dp[0] = 2Грабим дома [2, 7, 9]. Только первый даёт 2.
2. dp[1] = 7Берём лучшее из 2 и 7. Соседние дома вместе брать нельзя.
3. dp[2] = max(7, 2 + 9)Либо пропустить третий дом, либо взять его вместе с dp[0].
4. dp[2] = 11Выигрывает вариант с первым и третьим домом.
5. ответ = 11Три состояния, каждое посчитано ровно один раз.

function maxSubarraySum(nums) {
    let best = nums[0];
    let curr = nums[0];
    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        best = Math.max(best, curr);
    }
    return best;
}

Динамическое программирование (1-D): разбор примера

Наибольшая сумма непрерывного отрезка

Верните наибольшую сумму любого непрерывного отрезка массива.

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

Пусть состояние i это лучшая сумма отрезка, кончающегося на индексе i.

Либо прошлый отрезок продолжается, либо здесь начинается новый. Ответ это наибольшее состояние.

function maxSubArray(nums) {
    let best = nums[0];
    let endingHere = nums[0]; // only the previous state matters, so no array

    for (let i = 1; i < nums.length; i++) {
        // continue the stretch, or start a new one right here
        endingHere = Math.max(nums[i], endingHere + nums[i]);
        best = Math.max(best, endingHere);
    }

    return best;
}

Динамическое программирование (1-D): когда применять?

Эти формулировки в условии ведут сюда:

• •лучшее/максимум/минимум, заканчивающееся в позиции i
• •число способов дойти, подняться или замостить
• •нельзя брать два соседних элемента
• •минимальная стоимость пути по сетке
• •повторяющиеся подзадачи, одно и то же состояние считается заново

Динамическое программирование (1-D): с чем путают?

• Рекурсия с мемоизацией (Recursion with memoization): Мемоизация заполняет ту же таблицу сверху и по требованию. Здесь она заполняется снизу в заданном порядке.
• Жадный алгоритм (обменный аргумент) (Greedy (exchange argument)): Жадность выбирает один вариант на шаг. Динамика держит все варианты до конца.
• Рекурсия (Recursion): Рекурсия показывает, каким будет переход. Скорость даёт именно таблица.
• DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance)): Там состояние это пара позиций в двух последовательностях. Здесь хватает одного индекса.

Динамическое программирование (1-D): частые ошибки

• Состояние не определяет будущее

  Если две ситуации с одним состоянием ведут себя по-разному, состояние неполное. Добавьте недостающее.

• Заполняют таблицу в неверном порядке

  Ячейку надо записать до того, как её прочитают. Идите в направлении, которого требует переход.

• Читают ответом не ту ячейку

  Для состояния лучший-кончающийся-здесь ответом служит максимум. Это не последняя ячейка.

• Забывают базовые случаи

  Пустой вход или вход из одного элемента ломают большинство решений. Разберите их первыми.

Динамическое программирование (1-D): задачи с собеседований

• Подъём по лестнице: Каждая ступень приходит с одной или двух назад.
• Ограбление домов: Взять этот дом вместе с домом через один или пропустить.
• Максимальный подмассив: Продолжить отрезок или начать новый.
• Размен монет: Состояние это сумма, а каждая монета это ветка.
• Число способов расшифровки: Одна цифра или две, если пара допустима.
• Минимальная стоимость подъёма: Та же форма, но со стоимостью каждой ступени.
• Числа Фибоначчи: Самый короткий переход из всех возможных.

Динамическое программирование (1-D): сложность по времени и памяти

O(states)

n состояний по O(1) работы дают O(n). Память падает до O(1), когда важны только последние состояния.