Почему это работает
- Каждый подъём на ступень i заканчивается ровно одним последним шагом: на 1 с i − 1 или на 2 с i − 2. Значит, подъёмы делятся на две группы без общих элементов, и ways[i] = ways[i − 1] + ways[i − 2].
- ways[0] = 1 — пустой подъём, до первого шага. Шаг на 2 с земли на ступень 2 продолжает его, поэтому у ступени 2 способов 1 + 1 = 2, а не 1.
- Каждая клетка читает только две клетки перед собой, а они уже заполнены, так что хватает одного прохода слева направо. Перебор выписывает каждый подъём по отдельности, а их число растёт экспоненциально — так же быстро, как числа в клетках.
Сложность
Время O(n): каждая ступень заполняется один раз одним сложением. Память O(n) на таблицу; хватит и двух переменных для двух последних клеток, тогда O(1).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗