Встречаем первые «рабочие» выходные года новой задачкой. Эту задачу предлагали на собеседовании в Amazon.
Допустим, у нас есть лестница с N ступеньками. Вы начинаете снизу и можете шагнуть на 1 ступеньку вверх, либо на 2. Нужно написать функцию, которая, получая N, будет выдавать количество вариантов, которыми вы можете пройти снизу вверх.
Например, на рисунке N=3. Мы можем сделать 3 шага по 1 ступеньке (красная линия), шаг на 1 ступеньку, потом на 2 (зелёная), и шаг на 2, потом на 1 (синяя). Понятно, что мы не можем делать шаг на 2 ступеньки со второй, поскольку впереди только одна. Таким образом, у нас всего 3 варианта.
Усложнённый вариант задания: дан набор шагов, которые вы можете сделать. Например,
X = {1, 3, 5} – то есть вы можете сделать шаг на 1, 3 или 5 ступенек.Как обычно, приглашаю всех предлагать варианты решения в чате.