Определяем состояние DP

Динамическое программирование начинается не с массива dp, а с точного вопроса, на который будет отвечать одно состояние. Разберём его на количестве способов подняться на лестницу, делая шаг длиной 1 или 2.

Сколько способов добраться по ступеням

Для n ступеней найти число разных последовательностей шагов, ведущих на вершину. Для n = 4 это 1111, 112, 121, 211, 22, то есть 5 способов. Порядок шагов важен.

Как разрастается дерево всех шагов

Из текущей ступени можно выбрать шаг 1 или 2 и рекурсивно продолжить. Дерево содержит примерно 2^n узлов. Подзадача «сколько путей осталось с позиции 3» возникает из разных историй, хотя ответ у неё один.

Где рекурсия повторяет один и тот же хвост

Наивная рекурсия многократно вычисляет одинаковый хвост: ways(3) вызывает ways(2) и ways(1), а ways(2) снова вызывает ways(1). Число вызовов растёт как числа Фибоначчи.

Почему достаточно помнить оставшиеся ступени

Будущее зависит только от числа ступеней, которые ещё надо пройти, а не от маршрута до текущей позиции. Если осталось r ступеней, первый шаг либо 1, после чего остаётся r-1, либо 2, после чего остаётся r-2:

ways(r) = ways(r - 1) + ways(r - 2).

Это и есть состояние: r, а не весь список уже сделанных шагов.

Что именно хранит ячейка memo

memo[r] хранит точное число способов покрыть ровно r оставшихся ступеней. Если значение уже лежит в memo, повторный вызов не пересчитывает ни одну ветвь. Базы: ways(0) = 1 — один способ ничего не делать; ways(r < 0) = 0 — такой маршрут невозможен.

Как остановить повторные вызовы

1. Создать массив memo с признаком «ещё не вычислено».
2. Для r = 0 вернуть 1, для r < 0 вернуть 0.
3. Если memo[r] готов, вернуть его.
4. Записать в memo[r] сумму ответов для r-1 и r-2.

Как связать рекурсию с кэшем

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

C++17

#include <cassert>
#include <iostream>
#include <stdexcept>
#include <vector>

using namespace std;

long long countWays(int remaining, vector<long long>& memo) {
    if (remaining == 0) return 1;
    if (remaining < 0) return 0;
    if (memo[remaining] != -1) return memo[remaining];

    memo[remaining] = countWays(remaining - 1, memo) + countWays(remaining - 2, memo);
    return memo[remaining];
}

long long countWays(int stairs) {
    if (stairs < 0) throw invalid_argument("stairs must be non-negative");
    vector<long long> memo(stairs + 1, -1);
    return countWays(stairs, memo);
}

int main() {
    assert(countWays(0) == 1);
    assert(countWays(4) == 5);
    bool rejected = false;
    try {
        countWays(-1);
    } catch (const invalid_argument&) {
        rejected = true;
    }
    assert(rejected);
    cout << countWays(8) << '\n';
}

Python 3

def count_ways(stairs: int) -> int:
    if stairs < 0:
        raise ValueError("stairs must be non-negative")
    memo = [-1] * (stairs + 1)

    def solve(remaining: int) -> int:
        if remaining == 0:
            return 1
        if remaining < 0:
            return 0
        if memo[remaining] != -1:
            return memo[remaining]

        memo[remaining] = solve(remaining - 1) + solve(remaining - 2)
        return memo[remaining]

    return solve(stairs)


assert count_ways(0) == 1
assert count_ways(4) == 5
try:
    count_ways(-1)
    assert False, "negative stairs must be rejected"
except ValueError:
    pass
print(count_ways(8))

Сколько состояний действительно считается

Есть n + 1 состояний, каждое считает два перехода один раз: O(n) времени и O(n) памяти на memo плюс стек рекурсии. long long переполняется для достаточно больших n; если условие допускает большой ответ, нужны модуль или big integer. Подъём с отрицательным числом ступеней не имеет смысла и должен быть отсеян входной проверкой.

Какие значения ступеней требуют контракта

n = 0 — 1, не 0: пустая последовательность важна для рекуррентности. n = 1 — 1. Не забудьте, что шаг 2 из n = 1 ведёт в недопустимое -1. Для очень большого n рекурсивная версия может упереться в лимит стека Python, тогда нужна табуляция следующего урока.

Чем проверить мемоизированный подсчёт

• 0 -> 1, 1 -> 1, 2 -> 2, 4 -> 5;
• сравнить мемоизацию с полным перебором для n <= 10;
• проверить несколько повторных вызовов одной функции, чтобы memo не переносился между разными входами;
• проверить границу числового типа при большом n.

Когда повторяющийся остаток становится DP

Ищите рекурсивное дерево, в котором одинаковая «оставшаяся работа» возникает из разных путей. Если ответ определяется несколькими маленькими параметрами, а не всей историей, эти параметры — кандидат на состояние DP.

Когда одного remaining недостаточно

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

Самопроверка пустого маршрута

Вопрос: почему ways(0) равно 1?
Ответ: существует одна последовательность шагов, которая уже находится на вершине: пустая. Ноль сломал бы случаи, где последний шаг приводит ровно в вершину.

Самопроверка ключа кэша

Вопрос: почему ключ memo не должен включать весь путь вроде [1,2,1]?
Ответ: дальнейшее число способов определяется только оставшимися ступенями; разные пути с одинаковым остатком имеют одинаковый ответ.

Потренируйте новое состояние DP

Измените разрешённые шаги на 1, 3, 5. Сначала сформулируйте memo[r] одним предложением, затем выпишите базы и рекуррентность. Проверьте вручную n = 4: варианты должны различать порядок шагов.

Самостоятельный подсчёт вариантов

Решите без подсказок и до реализации одним предложением определите состояние каждой ячейки.

Задача 1

Разрешены шаги длиной 1, 3 и 5. Для неотрицательного n посчитайте число упорядоченных способов ровно попасть на ступень n. Определите поведение для отрицательного n.

Что делает состояние достаточным

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