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

O(states)

Заполните ряд ячеек dp[i], где каждая ячейка вычисляется из пары более ранних ячеек по одному правилу, рекуррентности. Один проход слева направо превращает экспоненциальный перебор в единственный проход за O(n).

Сигналы

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

Шаблон

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;
}

Похоже, но не то

Жадный алгоритм: Жадный алгоритм фиксирует то, что выглядит лучшим прямо сейчас, и больше не пересматривает выбор: это работает, только если доказать безопасность такого выбора обменным аргументом. Большинство задач подсчёта или оптимизации с пересекающимися состояниями требуют полной таблицы dp, потому что локально лучший выбор может закрыть путь к лучшему глобальному ответу.
Мемоизация: Мемоизация - та же рекуррентность, записанная сверху вниз: обычная рекурсивная функция плюс кэш уже решённых состояний. DP снизу вверх заполняет таблицу в фиксированном порядке, что избегает ограничений на глубину рекурсии и позволяет отбрасывать старые строки, если они больше не нужны.

n до 1e5..1e6, один проход слева направо, dp[i] считается по паре предыдущих ячеек -> O(n): каждое состояние вычисляется один раз за O(1).

Изучить этот паттерн