Climbing Stairs

Лёгкая№70одномерный массив

На лестнице n ступеней. За один шаг можно подняться на 1 или на 2 ступени. Сколькими разными последовательностями шагов можно подняться с земли на верхнюю ступень? Наш пример: n = 6 — способов 13.

70 Climbing StairsРазбор · 1×

Пример: n = 6. Сверху лестница, под ней таблица ways: сколько подъёмов заканчиваются на каждой ступени.

ступениways0123456
этот шагзаполненоберём отсюдаответ

Пустая таблица: клетка для земли (ступень 0) и по клетке на каждую из 6 ступеней

01/24
сначала · назад · пуск · шаг
Скорость
1function climbStairs(n):
2 ways = new array of size n + 1
3 ways[0] = 1 // the ground: no moves, one way
4 ways[1] = 1
5 for i from 2 to n:
6 one = ways[i - 1] // last move is 1 step
7 two = ways[i - 2] // last move is 2 steps
8 ways[i] = one + two
9 return ways[n]
состояние
ways
[–, –, –, –, –, –, –]
i
–
one
–
two
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждый подъём на ступень i заканчивается ровно одним последним шагом: на 1 с i − 1 или на 2 с i − 2. Значит, подъёмы делятся на две группы без общих элементов, и ways[i] = ways[i − 1] + ways[i − 2].
  2. ways[0] = 1 — пустой подъём, до первого шага. Шаг на 2 с земли на ступень 2 продолжает его, поэтому у ступени 2 способов 1 + 1 = 2, а не 1.
  3. Каждая клетка читает только две клетки перед собой, а они уже заполнены, так что хватает одного прохода слева направо. Перебор выписывает каждый подъём по отдельности, а их число растёт экспоненциально — так же быстро, как числа в клетках.

Сложность

Время O(n): каждая ступень заполняется один раз одним сложением. Память O(n) на таблицу; хватит и двух переменных для двух последних клеток, тогда O(1).

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.