Лестница и сочетания монет
Создавайте классические одномерные рекуррентные формулы с нуля
«Лестница и сочетания монет» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Знакомство с задачей о подъёме по лестнице
За один ход можно подняться на 1 или 2 ступеньки. Сколькими способами можно достичь ступеньки n? Этот классический пример одномерного DP фактически представляет собой числа Фибоначчи.
Найдите рекуррентное соотношение
Чтобы оказаться на ступеньке i, нужно прийти со ступеньки i-1 или i-2. Поэтому dp[i] = dp[i-1] + dp[i-2]: мы складываем оба возможных последних хода.
dp[i] = dp[i-1] + dp[i-2]Задайте базовые случаи
Есть один способ остаться на земле и один способ достичь ступеньки 1. Эти базовые случаи закладывают основу всей таблицы.
dp[0], dp[1] = 1, 1Заполните таблицу и прочитайте ответ
Двигайтесь снизу вверх — в последней ячейке будет находиться количество способов. Всё решение сводится к небольшому циклу табличного вычисления.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Сведите всё к двум переменным
Вам нужны только два последних значения, поэтому массив можно убрать. Эта версия с O(1) памяти особенно популярна на соревнованиях.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bПерейдите к комбинациям монет
Даны номиналы монет; посчитайте количество способов составить сумму A. Здесь порядок не имеет значения, поэтому мы считаем комбинации, а не последовательности.
coins = [1, 2, 5]Таблица комбинаций
Пусть dp[x] — количество способов получить сумму x. Начните с одного способа получить ноль: использовать пустое множество монет.
dp = [0]*(A+1)
dp[0] = 1Вынесите цикл по монетам наружу
Поместите цикл по монетам снаружи цикла по сумме. Такой порядок учитывает каждую комбинацию ровно один раз, не считая перестановки.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Комбинации и перестановки
Если поменять порядок циклов, Вы начнёте считать упорядоченные способы. Одна лишь вложенность циклов меняет смысл ответа.
Вариант задачи о размене монет с минимальным количеством
Чтобы найти минимальное количество монет, храните минимум, а не сумму. Инициализируйте значения бесконечностью и берите единицу плюс лучший результат для подзадачи.
dp[x] = min(dp[x], dp[x-c] + 1)Один шаблон, множество вариантов
Лестница и монеты имеют общую структуру: каждое состояние суммирует или минимизирует значения нескольких предыдущих состояний. Как только Вы это заметите, код почти напишется сам.
Быстрая проверка
При подсчёте комбинаций монет какой порядок циклов позволяет избежать повторов?
Итоги: складывайте последние ходы
Теперь Вы умеете решать задачи о лестнице и подсчёте монет с помощью одномерного рекуррентного соотношения. Каждый ответ складывает несколько более ранних состояний, а порядок циклов определяет, считаем ли мы комбинации или перестановки.
Часто задаваемые вопросы
Урок «Лестница и сочетания монет» бесплатный?
Да — полный текст урока «Лестница и сочетания монет» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Лестница и сочетания монет»?
Создавайте классические одномерные рекуррентные формулы с нуля Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Лестница и сочетания монет»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Мемоизация и табуляция
- Определение состояния и перехода
- Лестница и сочетания монет
- Наибольшая возрастающая подпоследовательность