Leetcode.com, задача №70. "Подъём по лестнице". Часть 2.

!!НАШ БЛОГ ПЕРЕЕХАЛ!!

Мы создали свой сайт! Все материалы, опубликованные в этом блоге, переехали туда.

Наш новый сайт maddevelop.ru

А данную статью вы можете найти по ссылке

Условие

Вы поднимаетесь по лестнице высотой n ступенек. За один шан Вы можете подняться или на 1 ступеньку, или на 2. Сколько вариантов подъёма существует?

Решение №4, число Фибоначчи

Ещё из третьего решения можно заметить, что при увеличении n каждое следующее количество вариантов равняется сумме двух предыдущих. Полученные числа, составляющие ряд, называются числами Фибоначчи. Поэтому мы можем перестать оперировать массивом и существенно уменьшить пространственную сложность.

public static int ClimbStairs(int n)
{
  if (n == 1)
    return 1;
  int first = 1;
  int second = 2;
  int third = 0;
  for (int i = 3; i <= n; i++)
  {
    third = first + second;
    first = second;
    second = third;
  }
  return third;
}

Временная сложность алгоритма: n. Используется цикл с n итерациями.

Пространственная сложность: 1. В программе используем всего лишь три переменных, сложность постоянна и не зависит от n.

Решение №5, метод Бине

В этом методе для нахождения n-го числа Фибоначчи используется матричное перемножение.

Временная сложность алгоритма: двоичный логарифм n.

Пространственная сложность: 1.

Решение №6, формула для расчёта числа Фибоначчи

Можно не вычислять самостоятельно число Фибоначчи, а воспользоваться следующей формулой:

public static int ClimbStairs(int n)
{
  double sqrt5 = Math.Sqrt(5);
  double fibn = Math.Pow((1 + sqrt5) / 2, n + 1) - Math.Pow((1 - sqrt5) / 2, n + 1);
  return (int)(fibn / sqrt5);
}

Временная сложность алгоритма: двоичный логарифм n. Столько времени занимает операция возведения в степень (Math.Pow).

Пространственная сложность: 1.

Источник:

https://leetcode.com/problems/climbing-stairs

Ещё больше интересной информации на нашем Telegram канале.