746. Min Cost Climbing Stairs — разбор задачи

Условие задачи

Дан массив cost: значение cost[i] означает стоимость ступеньки с индексом i. Стоя на ступеньке, мы платим её стоимость и можем подняться на одну или две ступеньки. Начать разрешено со ступеньки 0 или 1, а вернуть нужно минимальную общую стоимость подъёма на вершину. Условие на LeetCode

Вершина находится сразу после последней ступеньки, на позиции n = len(cost). Это не последний элемент массива: за саму вершину платить не нужно. Условие на LeetCode

Ограничения: 2 <= len(cost) <= 1000, 0 <= cost[i] <= 999. Пустого массива не бывает, зато нулевые стоимости разрешены. Условие на LeetCode

Где вершина и за что мы платим

Возьмём cost = [10, 15, 20]. Индексы ступенек: 0, 1, 2, а вершина находится на позиции 3.

Индекс:       0       1       2       3
Стоимость:   10      15      20    вершина

Начинаем:            1 ------------> 3
                     платим 15       финиш

Можно начать на ступеньке 1, заплатить 15 и сразу прыгнуть на вершину. Ответ: 15; ступеньку 2 мы не посещаем и её стоимость не платим. Пример на LeetCode

А вот прыжок со ступеньки 0 на две позиции приводит на ступеньку 2, а не на вершину. После оплаты 10 подъём ещё не закончен: со ступеньки 2 придётся уходить, заплатив ещё 20.

Во втором примере cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ответ равен 6. Один оптимальный маршрут: 0 → 2 → 4 → 6 → 7 → 9 → 10; оплачиваем шесть ступенек по единице. Пример на LeetCode

От полного перебора к динамическому программированию

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

Сначала определим, что именно считаем

Пусть dp(i) означает минимальную стоимость, чтобы оказаться на позиции i, ещё не оплачивая уход с неё. В ответ входят оплаты всех предыдущих ступенек маршрута, но не cost[i].

Поэтому dp(0) = dp(1) = 0: мы можем бесплатно выбрать стартовую позицию. Это не означает, что стартовая ступенька бесплатная: когда будем уходить с неё, её стоимость добавится в переходе.

На позицию i можно попасть только из двух мест:

Из i - 1: дойти до предыдущей ступеньки за dp(i - 1), оплатить cost[i - 1] и сделать шаг.
Из i - 2: дойти за dp(i - 2), оплатить cost[i - 2] и прыгнуть на две ступеньки.

Берём более дешёвый вариант:

[ dp(i) = \min\bigl(dp(i - 1) + cost[i - 1],\; dp(i - 2) + cost[i - 2]\bigr). ]

Именно такое состояние и переход использует официальный editorial. Ответом будет dp(n): минимальная стоимость, чтобы оказаться на вершине.

Решение в лоб: рекурсивно перебираем варианты

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

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        def dp(i: int) -> int:
            # На одну из стартовых позиций можно встать бесплатно
            if i < 2:
                return 0

            one_step = dp(i - 1) + cost[i - 1]
            two_steps = dp(i - 2) + cost[i - 2]
            return min(one_step, two_steps)

        return dp(len(cost))

Проблема не в формуле, а в повторениях. dp(5) вызывает dp(4) и dp(3), а dp(4) снова вызывает тот же dp(3). Дальше одни и те же подзадачи пересчитываются всё чаще.

dp(5)
├── dp(4)
│   ├── dp(3)
│   │   ├── dp(2)
│   │   └── dp(1)
│   └── dp(2)
└── dp(3)       та же подзадача ещё раз
    ├── dp(2)   и эта тоже
    └── dp(1)

Время растёт экспоненциально: грубая верхняя оценка O(2^N), более точная для этого дерева Θ(φ^N), где φ ≈ 1.618. Дополнительная память составляет O(N) из-за глубины рекурсии; это учебный перебор, а не решение для максимального ввода.

Мемоизация: каждую позицию считаем один раз

Результат dp(i) зависит только от i: массив cost в рамках вызова не меняется. Значит, ответ для уже посчитанной позиции можно сохранить и использовать повторно.

В Python для этого удобно добавить @cache. Тот же приём показан в официальном editorial.

from functools import cache
from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        @cache
        def dp(i: int) -> int:
            if i < 2:
                return 0

            one_step = dp(i - 1) + cost[i - 1]
            two_steps = dp(i - 2) + cost[i - 2]
            return min(one_step, two_steps)

        return dp(len(cost))

Теперь каждое из N + 1 состояний вычисляется не больше одного раза. Время: O(N); дополнительная память: O(N) на кеш и стек вызовов.

У рекурсивного Python-кода остаётся практическая оговорка: глубина вызовов линейная, и на длинном массиве можно упереться в лимит рекурсии. Поэтому этот вариант полезен для вывода идеи, а для отправки на LeetCode выберем итеративное решение ниже.

Табуляция: те же ответы, но обычным циклом

Вместо функции создадим массив dp длины n + 1. Смысл не меняется: dp[i] хранит минимальную стоимость, чтобы оказаться на позиции i, ещё не оплачивая уход с неё.

Начальные ответы уже известны: dp[0] = dp[1] = 0. Дальше считаем позиции по порядку от 2 до n: к моменту вычисления dp[i] оба нужных предыдущих ответа готовы.

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1)

        for i in range(2, n + 1):
            # Платим за ступеньку, с которой прыгаем
            one_step = dp[i - 1] + cost[i - 1]
            two_steps = dp[i - 2] + cost[i - 2]
            dp[i] = min(one_step, two_steps)

        return dp[n]

Время остаётся O(N), память тоже O(N), но рекурсивного стека больше нет. Обрати внимание: cost[n] нигде не читаем, хотя dp[n] вычисляем; вершина есть в массиве ответов, но её нет в массиве стоимостей.

Таблица вычислений

Проследим расчёт для cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]. Начальные значения: dp[0] = 0, dp[1] = 0.

Позиция `i`	Из `i - 1`: `dp[i - 1] + cost[i - 1]`	Из `i - 2`: `dp[i - 2] + cost[i - 2]`	`dp[i]`
2	`0 + 100 = 100`	`0 + 1 = 1`	1
3	`1 + 1 = 2`	`0 + 100 = 100`	2
4	`2 + 1 = 3`	`1 + 1 = 2`	2
5	`2 + 1 = 3`	`2 + 1 = 3`	3
6	`3 + 100 = 103`	`2 + 1 = 3`	3
7	`3 + 1 = 4`	`3 + 100 = 103`	4
8	`4 + 1 = 5`	`3 + 1 = 4`	4
9	`4 + 100 = 104`	`4 + 1 = 5`	5
10, вершина	`5 + 1 = 6`	`4 + 100 = 104`	6

Получили dp[10] = 6. Например, dp[8] = 4 не включает стоимость ступеньки 8: это цена прибытия на неё; чтобы уйти дальше, пришлось бы добавить cost[8] = 100.

Оптимальное решение: оставляем только два ответа

Для вычисления очередного dp[i] нужны только dp[i - 2] и dp[i - 1]. Всё, что было раньше, больше не используется, поэтому вместо массива достаточно двух переменных.

Назовём их prev2 и prev1. Перед очередной итерацией они хранят dp[i - 2] и dp[i - 1] соответственно; после вычисления нового ответа сдвигаем эту пару на одну позицию.

Алгоритм по шагам

Записать prev2 = 0 и prev1 = 0: это ответы для стартовых позиций.
Перебрать позиции i от 2 до n включительно.
Посчитать стоимость прихода из i - 1: prev1 + cost[i - 1].
Посчитать стоимость прихода из i - 2: prev2 + cost[i - 2].
Сохранить меньшую стоимость в current.
Сдвинуть ответы: prev2 = prev1, затем prev1 = current.
Вернуть prev1: после последней итерации это ответ для вершины.

Код на Python

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        prev2 = 0  # dp[0]
        prev1 = 0  # dp[1]

        for i in range(2, len(cost) + 1):
            one_step = prev1 + cost[i - 1]
            two_steps = prev2 + cost[i - 2]
            current = min(one_step, two_steps)

            # Сдвигаем пару только после вычисления нового ответа
            prev2 = prev1
            prev1 = current

        return prev1

Это основной вариант для собеседования: обычный цикл, понятный смысл переменных, без рекурсии и без изменения входного массива. Оптимизация совпадает с третьим подходом официального editorial.

Почему решение корректно

До начала цикла в переменных лежат правильные ответы для позиций 0 и 1. Предположим, что перед итерацией i значения prev2 и prev1 тоже правильные.

Любой маршрут на позицию i заканчивается прыжком из i - 2 или i - 1: других вариантов нет. Для каждого последнего прыжка мы берём лучший маршрут до его начала и добавляем стоимость ухода с этой ступеньки; минимум двух вариантов даёт лучший маршрут до i.

После сдвига переменные снова содержат два последних правильных ответа. Значит, на последней итерации вычисляем правильный ответ для позиции n, то есть для вершины.

Время и память

Время: O(N). Цикл выполняет N - 1 итераций, каждая содержит постоянное число операций.
Дополнительная память: O(1). Храним несколько чисел, не создаём массив DP и не используем рекурсивный стек.
Входной массив: не меняется. Копию cost тоже не создаём.

Краевые случаи

Две ступеньки: для [10, 15] ответ 10. Достаточно оплатить одну из стартовых ступенек и попасть на вершину; цикл делает ровно одну итерацию.
Все стоимости нулевые: для [0, 0, 0, 0] ответ 0. Ноль является полноценным результатом, а не признаком отсутствия ответа.
Дорогая последняя ступенька: для [1, 1, 999] ответ 1. Начинаем на позиции 1 и прыгаем сразу на вершину, не оплачивая последнюю ступеньку.
Все стоимости одинаковые: для [5, 5, 5, 5] ответ 10. Прыжки через ступеньку позволяют уменьшить число оплат.
Несколько оптимальных маршрутов: для [1, 1, 1] ответ 1. Возвращаем стоимость, поэтому выбирать один конкретный маршрут не требуется.

Почему не работает жадное решение

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

Контрпример: cost = [0, 1, 2, 100, 0]. Начнём на ступеньке 0; вершина находится на позиции 5.

Жадный маршрут: 0 → 1 → 2 → 4 → 5. Сначала выбираем стоимость 1 вместо 2, затем 2 вместо 100; суммарно платим 0 + 1 + 2 + 0 = 3.
Оптимальный маршрут: 0 → 2 → 4 → 5. Сразу идём на более дорогую ступеньку 2, зато не платим за ступеньку 1; итог 0 + 2 + 0 = 2.

Сравнивать только ближайшие cost недостаточно. DP сравнивает полную стоимость маршрутов, а не отдельные цены.

Подборка интересных решений

Ниже не новые «магические» алгоритмы, а полезные способы посмотреть на ту же динамику. Код адаптирован на Python с явными названиями и комментариями: сначала стоит понять основной вариант, а затем сравнить альтернативы.

Другая формула: ступенька уже оплачена

В популярных разборах avval на Java и Patrick на Python используется переход paid[i] = cost[i] + min(paid[i - 1], paid[i - 2]). Он отличается от нашей формулы, потому что состояние включает стоимость текущей ступеньки.

Пусть paid[i] означает минимальную стоимость, чтобы дойти до ступеньки i и уже оплатить её. Тогда paid[0] = cost[0], paid[1] = cost[1]; для второй базы важна неотрицательность стоимостей: начинать сразу на 1 не дороже, чем идти через 0.

На вершину можно попасть с любой из двух последних оплаченных ступенек. Поэтому ответ здесь не последний элемент DP, а минимум двух последних:

[ \min\bigl(paid[n - 2],\; paid[n - 1]\bigr). ]

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        paid2 = cost[0]
        paid1 = cost[1]

        for i in range(2, len(cost)):
            current = cost[i] + min(paid2, paid1)
            paid2 = paid1
            paid1 = current

        # Обе последние ступеньки позволяют попасть на вершину
        return min(paid2, paid1)

Время: O(N), дополнительная память: O(1), вход не меняется. Для [10, 15, 20] оплаченные стоимости равны [10, 15, 30], поэтому ответ min(15, 30) = 15.

Две формулы не противоречат друг другу. Для настоящей ступеньки paid[i] = dp[i] + cost[i]: одна величина включает оплату текущей ступеньки, другая нет.

Обратный проход: сколько осталось заплатить

Clayton Wong в The ART of dynamic programming строит решения от стоимости оставшегося пути, включая реализации на Python, JavaScript, Kotlin и C++. Здесь естественно считать не «как дойти до i», а «сколько стоит подняться на вершину, если сейчас стоим на i».

Назовём этот ответ remaining[i]. Нужно оплатить текущую ступеньку, а затем выбрать лучший из двух будущих путей:

[ remaining[i] = cost[i] + \min\bigl(remaining[i + 1],\; remaining[i + 2]\bigr). ]

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

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        next1 = 0  # Стоимость оставшегося пути с позиции i + 1
        next2 = 0  # Стоимость оставшегося пути с позиции i + 2

        for i in range(len(cost) - 1, -1, -1):
            current = cost[i] + min(next1, next2)
            next2 = next1
            next1 = current

        # Можно начать с позиции 0 или 1
        return min(next1, next2)

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

Для [10, 15, 20] получаем оставшиеся стоимости [25, 15, 20] и ответ min(25, 15) = 15. Время: O(N), дополнительная память: O(1), вход не меняется.

В разборе niits обратный проход реализован с добавлением нуля в конец cost и перезаписью самого массива. Идея та же, но добавлять элемент во вход не обязательно: две переменные дают решение без побочных эффектов.

Короткое in-place решение

В популярном C++-решении Bhairav Jangid сам массив cost используется как таблица оплаченных стоимостей. На Python тот же приём выглядит так:

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(2, len(cost)):
            # Теперь cost[i] хранит ответ, а не исходную цену
            cost[i] += min(cost[i - 1], cost[i - 2])

        return min(cost[-2], cost[-1])

Время: O(N), дополнительная память: O(1). Но входной массив меняется: [10, 15, 20] превратится в [10, 15, 30], и повторный вызов на том же объекте будет решать уже другую задачу.

Если сначала сделать cost = cost.copy(), побочного эффекта не будет, но дополнительная память станет O(N). Для этой задачи компромисс не нужен: основной вариант с двумя переменными уже сохраняет вход и использует O(1) памяти.

Что полезно забрать из объяснений сообщества

Лестница оптимизаций у avval: рекурсия, мемоизация, массив DP, два последних значения. Хороший способ объяснить, откуда получается короткий код, а не просто предъявить его. Разбор avval
Вывод состояния у Ryan: сначала определить смысл функции, затем переход и базы. Важно: показанный в посте рекурсивный код без кеша остаётся полным перебором, а не линейным DP-решением; это отдельно отмечено в комментариях. Разбор Ryan и комментарии
Первые состояния у Patrick: вручную выписать ответы для первых ступенек и увидеть закономерность. Полезно для знакомства с DP, но нужно проговорить, что текущая ступенька уже оплачена. Разбор Patrick

Грабли из editorial и комментариев

Не смешивать определения DP

В комментариях к официальному editorial обсуждают, почему начальные значения равны нулю и почему в переходе добавляется стоимость предыдущей ступеньки. Обе детали становятся понятными, если сначала зафиксировать: наше состояние означает прибытие без оплаты текущей ступеньки.

Смысл состояния	Начальные значения	Переход	Ответ
Прибыли на `i`, текущая ступенька не оплачена	`dp[0] = dp[1] = 0`	`min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])`	`dp[n]`
Прибыли на `i` и оплатили её	`paid[0] = cost[0]`, `paid[1] = cost[1]`	`cost[i] + min(paid[i - 1], paid[i - 2])`	`min(paid[n - 2], paid[n - 1])`
Стоим на `i`, считаем оставшийся путь	Нули для вершины и технической позиции за ней	`cost[i] + min(remaining[i + 1], remaining[i + 2])`	`min(remaining[0], remaining[1])`

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

Ноль нельзя использовать как «ещё не посчитано»

В Java-коде мемоизации из разбора avval кеш проверяется условием dp[n] != 0. Однако нулевые стоимости разрешены условием задачи. Ограничения LeetCode

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

При ручной мемоизации нужно отличать отсутствие значения от любого допустимого ответа. Подойдут None, отдельный массив посещённых состояний или проверка наличия ключа в словаре; @cache тоже не путает эти ситуации.

Не забывать последний переход

В основном решении цикл идёт до n включительно: range(2, n + 1). Если остановиться на n - 1 и вернуть последнее значение, получится стоимость прибытия на последнюю ступеньку, а не на вершину.

При сжатии памяти нельзя раньше времени перезаписать предыдущий ответ. Сначала вычисляем current по двум старым значениям, только потом сдвигаем переменные.

Вывод

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

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

🐆