# 70 Подъем по лестнице

Проблема



Подъем по лестнице - LeetCode
Повысьте свои навыки программирования и быстро получите работу. Это лучшее место, чтобы расширить свои знания и подготовиться… leetcode.com



Вы поднимаетесь по лестнице. Чтобы достичь вершины, нужно сделать n шаг.

Каждый раз вы можете подниматься по 1 или 2 ступеням. Какими разными способами вы можете подняться на вершину?

Пример:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Псевдокод

Ключевым моментом является то, что мы смотрим вниз, например. сейчас мы стоим на 6-й ступеньке, единственные два варианта, которые мы могли бы сделать: сделать 1 шаг от 5-й ступени, сделать 2 шага от 4-й ступеньки.

  1. n = 6, возможные варианты = 4-й + 5-й;
  2. n = 5, возможные способы = 3-й + 4-й
  3. n = 4, возможные способы = 2-й + 3-й
  4. n = 3, возможные способы = 2-й + 1-й
  5. n = 2, возможных способов = 2
  6. n = 1, возможных способов = 1

В заключение, это на самом деле ряд Фибоначчи.

n(6) = n(4) + n(5)
n(5) = n(4) + n(3)
n(4) = n(3) + n(2)

код