#013 Сколько существует способов добраться до N-й ступеньки?

Начало здесь простое. Вы стоите на лестничном марше и хотите подняться на первую ступеньку — № 1. Для этого надо сделать всего одно действие — подняться на одну ступеньку вверх. Теперь давайте рассмотрим вторую ступеньку, то есть N = 2. Чтобы подняться на неё, имеются два варианта. Вы можете сделать два шага — по одной ступеньке за раз или сразу подняться на вторую ступеньку.

Это практически вся информация, которая нужна вам для решения этой задачи. Чтобы понять, почему, представьте, что вашей целью является ступенька № 3. Впервые в этой ситуации вы не можете попасть на неё одним движением. здесь потребуется комбинация шагов. Существует только два способа попадания на ступеньку № 3: либо в виде короткого одиночного шага (со ступеньки № 2), либо двойного шага (со ступеньки № 1). Мы уже знаем, что для подъема на ступеньку № 1 имеется лишь один вариант. Мы также знаем, что есть всего два способа подняться на ступеньку № 2. Сложите эти варианты (1 + 2 = 3), и вы получите число способов, позволяющих подняться на ступеньку № 3.

Та же самая логика применяется для подъема на каждую следующую ступеньку. Существует два способа, чтобы подняться на ступеньку № 4 — со ступеньки № 2 или со ступеньки № 3. Добавьте число способов подъема на ступеньку № 2 (2) к числу способов, позволяющих оказаться на ступеньке № 3 (3). Это даёт 5 вариантов — число способов, позволяющих оказаться на ступеньке № 4.

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

Любому человеку с математической подготовкой нижняя серия покажется до боли знакомой. Это последовательность Фибоначчи. Таким образом количество способов добраться до N-ой ступеньки это просто число Фибоначчи под номером N.