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

Вычислим F(5): F(4)+F(3). Для F(4) снова нужны F(3)+F(2), так что F(3) решается дважды. Его ветви тоже повторяются. На рисунке нажмите F(3), чтобы увидеть одинаковые подзадачи. Наша цель — выполнять работу для каждого аргумента один раз.

Динамическое программирование (Dynamic programming) — Метод решения задачи через сохранение ответов на повторяющиеся подзадачи и переходы между ними.

Карта решения: к этим вопросам возвращайтесь в каждой новой задаче на динамическое программирование.

Наивная рекурсия F(n) = F(n−1) + F(n−2) повторно вычисляет одни и те же подзадачи. Дерево вызовов разрастается экспоненциально.

fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

Для F(5) дерево содержит 15 вызовов, но всего 6 разных аргументов: 0…5. Три вызова F(2) решают одну и ту же подзадачу. Запоминание ответов сокращает повторную работу. Теперь, после примера, соберём вопросы, с которых будем начинать собственное ДП. В задачах о путях база будет другой: её нельзя копировать из Фибоначчи.

Проблема не в рекурсии как таковой, а в повторном решении одних состояний. Сохраним их ответы.

Дерево вызовов содержит повторы, а множество разных аргументов мало. Запомним результат первого вычисления каждого аргумента и будем возвращать его при повторном запросе.

Мемоизация (Memoization) — Кэширование результатов рекурсивных подзадач при первом обращении.

Перед рекурсивным вычислением fib(n) проверяем кэш: если ответ есть, возвращаем его сразу. Так получаем O(n) состояний вместо экспоненциального числа рекурсивных вызовов.

memo = array(n+1, UNSET)
fib(k):
    if memo[k] != UNSET: return memo[k]
    if k < 2: ans = k
    else: ans = fib(k-1) + fib(k-2)
    memo[k] = ans
    return ans

Это top-down DP: дерево рекурсивных запросов вычисляет только действительно нужные состояния и больше не пересчитывает их.

Ключ кэша должен полностью описывать подзадачу: одного номера клетки не хватит, если ещё важен оставшийся ресурс. Отсутствующий результат лучше отмечать None/Option или отдельным флагом, поскольку ноль может быть корректным ответом. Кэш не устраняет глубину рекурсии: цепочка из 200 000 состояний всё ещё опасна для стека Python.

def fib_memo(n):
    memo = [None] * (n + 1)
    def solve(k):
        if memo[k] is not None: return memo[k]
        memo[k] = k if k < 2 else solve(k - 1) + solve(k - 2)
        return memo[k]
    return solve(n)

def fib_iter(n):
    if n == 0: return 0
    a, b = 0, 1
    for _ in range(1, n): a, b = b, a + b
    return b

print(fib_memo(10), fib_iter(10))

fn fib_memo(n:usize)->u64{
    assert!(n<=93);
    fn solve(k:usize,memo:&mut[Option<u64>])->u64{if let Some(value)=memo[k]{return value;}let value=if k<2{k as u64}else{solve(k-1,memo)+solve(k-2,memo)};memo[k]=Some(value);value}
    solve(n,&mut vec![None;n+1])
}
fn fib_iter(n:usize)->u64{assert!(n<=93);if n==0{return 0;}let(mut a,mut b)=(0,1);for _ in 1..n{(a,b)=(b,a+b);}b}
fn main(){println!("{} {}",fib_memo(10),fib_iter(10));}

55 55

Каждое состояние теперь вычисляется один раз. Попробуем задать порядок вычислений явно и уменьшить память.

Мемоизация сохраняет форму рекурсивного решения. Но если порядок зависимостей известен заранее, можно вообще отказаться от рекурсивного стека и заполнить ответы от маленьких состояний к большим.

Табуляция (Bottom-up DP) — Вычисление состояний в таком порядке, чтобы все зависимости уже были известны.

Сначала создадим dp[0…n]: dp[0]=0, при n≥1 dp[1]=1. Для i от 2 до n запишем dp[i]=dp[i−1]+dp[i−2]. На n=6 таблица получается [0,1,1,2,3,5,8]. Только после заполнения заметим, что для следующего значения нужны две последние ячейки.

if n == 0: return 0
a, b = 0, 1
for i = 2..n:
    a, b = b, a + b
return b

Перед итерацией i переменные a и b должны хранить F(i−2) и F(i−1). Сначала считаем новое значение из старых, затем сдвигаем пару. Память O(1) достаточна для самого числа, но не для выдачи всех значений или восстановления маршрута. Оценка O(n) времени предполагает арифметику фиксированной стоимости; точные большие целые требуют учитывать длину чисел.

Механизм ДП понятен. Дальше научимся получать состояние и формулу из условия задачи, а не из готовой последовательности.

Числа Фибоначчи были примером готовой формулы. Теперь выведем рекуррентность из условия задачи: кенгуру прыгает по клеткам на один или два шага. Начнём с точного смысла одного состояния.

Есть ряд клеток. Из каждой можно перепрыгнуть на одну или две клетки; задача — посчитать, сколькими способами можно попасть в последнюю. Каждый путь в i оканчивается прыжком из i−1 или из i−2.

Если разрешены прыжки 1…k, формула обобщается до суммы k предыдущих состояний, что даёт прямую реализацию за O(nk). При необходимости скользящая сумма снижает время до O(n).

Пусть d[i] — число способов попасть ровно в i. В нулевой клетке есть один пустой маршрут, поэтому d[0]=1. Последний прыжок из i−1 и последний прыжок из i−2 образуют непересекающиеся классы путей — их количества складываются. Для запретной клетки ставим 0. При вычислении по модулю берём остаток после каждого сложения.

Сложение объединило количества маршрутов. Для оптимизации заменим его минимумом и сохраним лучший переход.

def jump_ways(n, blocked):
	# Напишите решение
	pass

Вместо количества путей попросим самый дешёвый маршрут. Граф допустимых прыжков тот же; меняется операция, которая объединяет ответы предшественников.

Если у каждой клетки есть цена c[i], надо найти маршрут с минимальной суммой цен. Вместо суммы количества способов используем минимум стоимости.

Для восстановления ответа храним p[i] — предшествующую клетку, из которой получен оптимум. Начав с конечной клетки, переходим по p до начала и разворачиваем маршрут.

В нашем примере старт находится в клетке 0 и его цена оплачивается: d[0]=c[0], d[1]=c[1]+d[0]. Это отличается от задач, разрешающих начать с клетки 1 бесплатно. Храним p[i], выбранного предшественника, затем идём от финиша до старта и разворачиваем путь. При равенстве стоимостей можно выбрать любого оптимального предка, если условие не требует особого порядка.

def mincost_path(cost):
    if not cost: return 0, []
    dp, parent = cost.copy(), [-1] * len(cost)
    for i in range(1, len(cost)):
        p = i - 2 if i >= 2 and dp[i-2] <= dp[i-1] else i - 1
        dp[i], parent[i] = cost[i] + dp[p], p
    path, i = [], len(cost) - 1
    while i != -1:
        path.append(i)
        i = parent[i]
    return dp[-1], path[::-1]

value, path = mincost_path([3, 7, 2, 5, 1, 4])
print(value)
print(*path)

fn mincost_path(cost:&[i64])->(i64,Vec<usize>){
    if cost.is_empty(){return(0,vec![]);}
    let mut dp=cost.to_vec();let mut parent=vec![None;cost.len()];
    for i in 1..cost.len(){let p=if i>=2&&dp[i-2]<=dp[i-1]{i-2}else{i-1};dp[i]=cost[i]+dp[p];parent[i]=Some(p);}
    let mut path=Vec::new();let mut current=Some(cost.len()-1);
    while let Some(i)=current{path.push(i);current=parent[i];}path.reverse();(dp[cost.len()-1],path)
}
fn main(){let(value,path)=mincost_path(&[3,7,2,5,1,4]);println!("{}",value);println!("{}",path.iter().map(|x|x.to_string()).collect::<Vec<_>>().join(" "));}

10
0 2 4 5

Оптимальный маршрут восстановлен. Теперь отделим сам граф переходов от направления, в котором выполняются обновления.

def min_cost(cost):
	# Напишите решение
	pass

d = array(n+1, 0)
d[0] = 1
for i = 1..n:
    d[i] = d[i-1]
    if i >= 2: d[i] += d[i-2]

До сих пор мы собирали ответ клетки из уже посчитанных предков. Можно взглянуть на те же рёбра в обратную сторону: из готового состояния раздать вклад будущим. Смысл состояния и зависимости при этом не меняются.

Переход состояния (Transition) — Правило, вычисляющее вклад других состояний в текущее или будущие состояния.

Просмотр назад (gather): для текущего i перебрать все возможные состояния-предшественники и собрать ответ. Просмотр вперёд (scatter): для уже посчитанного i обновить все достижимые следующие состояния.

В обоих случаях нужен корректный порядок обработки, обеспечивающий отсутствие зависимостей от ещё не вычисленных ответов. Для направленного ациклического графа это топологический порядок.

d = array(n, 0)
d[0] = 1
for i = 0..n-1:
    if i+1 < n: d[i+1] += d[i]
    if i+2 < n: d[i+2] += d[i]

В переходе вперёд нельзя обновить получателя и сразу обработать его раньше всех остальных предков: иначе часть вклада потеряется. На линии и в таблице естественный порядок очевиден; в общем ациклическом графе нужен топологический. При циклах однократного обхода может быть недостаточно: это уже другая постановка.

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

Добавим вторую координату. Робот идёт по таблице только вправо и вниз, а некоторые клетки закрыты. Номер состояния теперь пара (строка, столбец), но порядок рассуждения остаётся прежним.

В двумерной решётке, где можно ходить только вправо и вниз, число способов попасть в клетку равно сумме способов попасть в её верхнего и левого соседей.

Обход строками сверху вниз и столбцами слева направо гарантирует, что оба предшественника уже известны. Время и память — O(rows · cols).

Закрытая стартовая клетка даёт ноль маршрутов, открытая таблица 1×1 — один. В строковом обходе вектор dp[j] до обновления хранит ответ сверху, а dp[j−1] — уже обновлённый ответ слева. Так память сокращается до O(cols), но восстановление конкретного пути потребует дополнительных данных или повторного вычисления.

def grid_paths(blocked):
    if not blocked or not blocked[0]: return 0
    cols = len(blocked[0])
    dp = [0] * cols
    dp[0] = 1
    for row in blocked:
        for j in range(cols):
            if row[j]: dp[j] = 0
            elif j: dp[j] = (dp[j] + dp[j-1]) % 1_000_000_007
    return dp[-1]

print(grid_paths([[0,0,0],[0,1,0],[0,0,0]]))

fn grid_paths(blocked:&[Vec<bool>])->u64{
    if blocked.is_empty()||blocked[0].is_empty(){return 0;}
    let cols=blocked[0].len();let mut dp=vec![0;cols];dp[0]=1;
    for row in blocked{for j in 0..cols{if row[j]{dp[j]=0;}else if j>0{dp[j]=(dp[j]+dp[j-1])%1_000_000_007;}}}dp[cols-1]
}
fn main(){println!("{}",grid_paths(&[vec![false,false,false],vec![false,true,false],vec![false,false,false]]));}

2

Основной инструмент готов: состояние, база, переход и порядок заполнения. Теперь создайте собственное ДП в практике. Для очень далёких одинаковых шагов ниже доступно дополнительное исследование матриц.

def grid_paths(blocked):
	# Напишите решение
	pass

Справочник собирает определения из разобранных разделов. Используйте поиск, если нужно восстановить термин; затем переходите к оценке ограничений и задачам для самостоятельного решения.

Общий справочник всех лекций ↗

Найдено: 13 из 13

Сначала подставьте максимальные размеры из условия в оценку времени и памяти. Оценка числа действий — ориентир: константы, язык и ввод проверяются отдельно.

Число состояний × работа переходов

Для линии с n = 200 000 и двумя предками получается O(n). Для n = 200 000 и k = 200 000 полный перебор k прыжков на каждом состоянии даст до 4·10¹⁰ переходов. Маленькое тело цикла не компенсирует такое число повторений.

Таблица и память

Для 1000×1000 клеток нужен миллион состояний. Один массив i64 занимает примерно 8 МБ, четыре таких массива — 32 МБ без дополнительного хранения поля. В Python список списков с отдельными int имеет гораздо больший расход. Если нужны только значения соседних строк, переходите к O(cols) памяти.

В задаче Working out нужны ответы из четырёх направлений, поэтому одной строки на всё решение недостаточно. Сначала выпишите, какие промежуточные значения понадобятся на этапе соединения маршрутов.

Разрядность, рекурсия и большое n

Число путей растёт быстро. Если условие требует модуль, применяйте его к каждому обновлению; если точный ответ — оцените длину больших целых. Сумма цен до 10⁹ на пути из 200 000 клеток требует i64. Нельзя использовать 0 как недостижимость, когда ответ 0 допустим.

Top-down с глубиной 200 000 опасен для Python. Bottom-up убирает этот риск. Для n до 10¹⁸ фиксированная матрица размера s требует O(s³ log n), но только при действительно одинаковом линейном переходе. Проверьте нулевой шаг, закрытый старт, одну клетку, равные оптимумы и отсутствие маршрута.

def jump13_ways(n, forbidden):
	# Сначала перенесите свою базу и переход
	pass

Основное применение

После конструктора решите Climbing Stairs и Min Cost Climbing Stairs: одинаковые направления прыжков дают разные смысл состояния и базу. Затем перенесите вывод на таблицу. Сложное испытание объединяет несколько направлений и остаётся дополнительным.

Примените разобранные приёмы самостоятельно. Для каждой задачи сначала сформулируйте требования к ответу и предложите простое решение. Затем подставьте максимальные ограничения, оцените время и память и решите, какое улучшение требуется. Подсказки с идеей и оценкой раскрываются отдельно.

Уровни задают порядок практики в курсе, а не единую шкалу платформ. Если уровень отличается от отметки LeetCode, это указано в карточке. Для Codeforces используется оценка курса.

Дальше применяйте тот же конструктор к рюкзаку и подпоследовательностям: начните с вопроса, какие параметры полностью определяют подзадачу. Матричное ускорение выше пригодится отдельно для постоянных линейных переходов.