Переход, база и порядок вычисления

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

Как пройти лестницу с минимальной ценой

Есть cost[i] — цена приземления на ступень i. Начать можно перед первой ступенью, а закончить нужно за последней. Найти минимальную сумму. Для [10, 15, 20] выгодно наступить на 10, затем на 20, ответ 15? Нет: стартовать можно с 0-й или 1-й ступени, поэтому оптимально начать с 15 и уйти за массив: ответ 15.

Что перебирает каждая последовательность шагов

Из позиции i рекурсивно попробовать следующий прыжок на i+1 и i+2, сложить цену приземления и выбрать меньший путь. Разные маршруты много раз приходят к одной позиции, поэтому ветвей экспоненциально много.

Почему одинаковые позиции считаются снова

Функция «минимальная цена до позиции i» вычисляется повторно. Нам не нужен порядок маршрута, только минимальная цена для каждой уже достигнутой позиции.

Как прошлые две позиции определяют текущую цену

Чтобы приземлиться на i, последний шаг был из i-1 или i-2. Значит, dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Для ступеней 0 и 1 цена — соответственно cost[0] и cost[1]. Чтобы выйти за массив, можно сделать последний шаг из одной из двух последних ступеней.

Что гарантирует заполненная строка dp

После заполнения dp[0..i] каждое dp[j] содержит минимальную стоимость попасть на ступень j. При вычислении dp[i] переходы dp[i-1] и dp[i-2] уже готовы, поэтому один проход слева направо корректен.

В каком порядке считать стоимость подъёма

1. Если ступеней 0 или 1, плата не нужна: можно перешагнуть массив.
2. Заполнить базы dp[0] и dp[1].
3. Для i от 2 до n-1 вычислить формулу перехода.
4. Вернуть min(dp[n-1], dp[n-2]) — последний прыжок выходит за верх.

Как не перепутать индексы ступеней

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

C++17

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

int minClimbCost(const vector<int>& cost) {
    int n = static_cast<int>(cost.size());
    if (n <= 1) return 0;

    vector<int> dp(n);
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < n; ++i) {
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
    }
    return min(dp[n - 1], dp[n - 2]);
}

int main() {
    assert(minClimbCost({10, 15, 20}) == 15);
    assert(minClimbCost({1, 100, 1, 1, 1, 100, 1, 1, 100, 1}) == 6);
    cout << minClimbCost({5, 6}) << '\n';
}

Python 3

def min_climb_cost(cost: list[int]) -> int:
    if len(cost) <= 1:
        return 0

    dp = [0] * len(cost)
    dp[0] = cost[0]
    dp[1] = cost[1]
    for index in range(2, len(cost)):
        dp[index] = cost[index] + min(dp[index - 1], dp[index - 2])
    return min(dp[-1], dp[-2])


assert min_climb_cost([10, 15, 20]) == 15
assert min_climb_cost([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]) == 6
print(min_climb_cost([5, 6]))

Как сжать память табуляции

Время O(n), память O(n) на таблицу. Если нужен только ответ, память можно сжать до O(1), сохраняя две предыдущие цены. Цены предполагаются конечными целыми; для больших значений в C++ используйте long long. Эта формулировка разрешает старт с первой или второй ступени.

Где короткая лестница ломает индексы

При пустом массиве и одном элементе можно сразу выйти, ответ 0. Для двух элементов выбирается меньшая цена. Отрицательные цены математически работают, но могут менять интуицию: стоит явно сверить их с условием. Ошибка на базе dp[0] = 0 неверно делает первую ступень бесплатной.

Какими стоимостями проверить переход

• [] -> 0, [7] -> 0, [5,6] -> 5;
• [10,15,20] -> 15;
• чередование дешёвых и дорогих ступеней;
• сравнение со всеми путями для n <= 12;
• случай с равными двумя вариантами перехода.

Когда ответ строится слева направо

Ищите последовательность позиций, где ответ в текущей позиции зависит от малого числа предыдущих позиций: «можно прыгнуть на 1 или 2», «минимальная цена до дня i», «лучший результат на префиксе». Переход сам подсказывает порядок: зависимости слева — проход слева направо.

Когда порядок табуляции другой

Не заполняйте таблицу слева направо, если переход смотрит в будущее или образует цикл. Если выбор зависит от ещё одного параметра, например оставшихся купонов, одномерного dp[i] недостаточно. Не забывайте проверить, разрешён ли старт именно с двух первых ступеней.

Самопроверка базы таблицы

Вопрос: почему ответ — min(dp[n-1], dp[n-2]), а не dp[n-1]?
Ответ: на верх можно уйти шагом длины 1 с предпоследней ступени или шагом 2 с последней; не обязательно наступать на последнюю.

Самопроверка последнего перехода

Вопрос: почему цикл начинается с i = 2?
Ответ: только с этого индекса существуют обе зависимости i-1 и i-2; первые два состояния являются базой задачи.

Потренируйте заполнение по порядку

Добавьте разрешённый прыжок на 3 ступени. Сначала напишите новый переход и минимальный набор баз. Проверьте его на [10, 100, 100, 1]: ответ должен показать, действительно ли можно перепрыгивать дорогие ступени.

Самостоятельная табуляция без подсказок

Не открывайте решения до того, как назовёте базовые значения и направление всех зависимостей.

Задача 1

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

Что доказывает порядок заполнения

Табуляция — это не «цикл вместо рекурсии». Сначала определите, что хранит ячейка, затем её зависимости, базы и только после этого выберите направление заполнения.