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

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

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

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

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

Условие

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

Пример №1

Количество ступенек: 2

Количество вариантов: 2

Один шаг на 1 ступеньку и ещё один на 1 (1 + 1).
Шаг сразу на 2 ступеньки (2).

Пример №2

Количество ступенек: 3

Количество вариантов: 3

1 + 1 + 1
1 + 2
2 + 1

Решение №1, методом перебора

Воспользуемся возвращающей количество вариантов подъёма рекурсивной функцией ClimbStairs(int i, int n), где i - количество пройденных ступенек, n - количество ступенек в лестнице.

public static int ClimbStairs(int i, int n)
  {
  if (i > n)
    return 0;
  if (i == n)
    return 1;
  return ClimbStairs(i + 1, n) + ClimbStairs(i + 2, n);
}

Поясним работу алгоритма с рекурсией для лестницы с 3 ступеньками. Следовательно, функция с параметрами будет выглядеть как ClimbStairs(0, 3).

вызов функции ClimbStairs(0, 3)  // 1 вызов
i = 0
return ClimbStairs(1, n) + ClimbStairs(2, n)
  
  вызов функции ClimbStairs(1, n)  // 2 вызов
  i = 1
  return ClimbStairs(2, n) + ClimbStairs(3, n)
    
    вызов функции ClimbStairs(2, n)  // 3 вызов
    i = 2
    return ClimbStairs(3, n) + ClimbStairs(4, n)
    
      вызов функции ClimbStairs(3, n)  // 4 вызов            
      i = 3
      return 1

      вызов функции ClimbStairs(4, n)  // 5 вызов
      i = 4
      return 0

    результатом 3 вызова, функции ClimbStairs(2, n), будет 1 = 1(4 вызов) + 0(5 вызов) 
  
  выполнение переходит ко 2 вызову, к слагаемому ClimbStairs(3, n)

    вызов функции ClimbStairs(3, n)  // 6 вызов
    i = 3
    return 1
  
  результатом 2 вызова, функции ClimbStairs(1, n), будет 2 = 1(3 вызов) + 1(6 вызов)

выполнение переходит к 1 вызову, к слагаемому ClimbStairs(2, n)

  вызов функции ClimbStairs(2, n)  // 7 вызов
  i = 2
  return ClimbStairs(3, n) + ClimbStairs(4, n)
    
    вызов функции ClimbStairs(3, n)  // 8 вызов
    i = 3
    return 1

    вызов функции ClimbStairs(4, n)  // 9 вызов
    i = 4
    return 0

  результатом 7 вызова, функции ClimbStairs(2, n), будет 1 = 1(8 вызов) + 0(9 вызов)
  
выполнение переходит к 1 вызову
результатом и ответом задачи будет 3 = 2(2 вызов) + 1(7 вызов)

Временная сложность данного алгоритма: 2 в степени n.

Пространственная сложность: n, глубина рекурсии зависит от количества элементов.

Решение №2, рекурсия с мемоизацией.

В описании рекурсивного метода предыдущего решения можно заметить, что функции ClimbStairs(2, n), ClimbStairs(3, n) и ClimbStaits(4, n) вызываются несколько раз. Для ускорения алгоритма можно записывать результат выполнения функции в массив и при повторном вызове брать из него вычисленный результат. Данный способ, предназначенный для ускорения работы алгоритмов, называется мемоизацией.

int[] memo = new int[n];
public static int ClimbStairs(int i, int n, int[] memo)
{
  if (i > n)
    return 0;
  if (i == n)
    return 1;
  if (memo[i] > 0)
    return memo[i];
  memo[i] = ClimbStairs(i + 1, n, memo) + ClimbStairs(i + 2, n, memo);
  return memo[i];
}

Видно, что если пройденный путь (i < n) меньше количества ступенек и данная функция не высчитывалась (memo[i] = 0), то происходит запись результат вызова функции (memo[i] = ...).

Временная сложность алгоритма: n.

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

Скорость выполнения стремительно возрастает по сравнению с решением №1. Для лестницы с 40 ступеньками первое решение выполняется за 11 с, а второе - менее 1 мс! Недостатком данного алгоритма является использование дополнительной памяти в виде массива memo.

Решение №3, динамическое программирование.

Логично, что достигнуть i-й ступеньки мы можем сделав шаг со ступеньки i - 1 и со ступеньки i - 2. Поэтому для нахождения всех вариантов пути достаточно сложить варианты путей для достижения двух предыдущих ступенек. Данную закономерность можно увидеть, посчитав количество путей для лестниц с небольшим количеством ступенек: 1 - 1, 2 - 2, 3 - 3, 4 - 5, 5 - 8, 6 - 13.

public static int DynamicClimbStairs(int n)
{
  if (n == 1)
    return 1;
  int[] dp = new int[n + 1];
  dp[1] = 1;
  dp[2] = 2;
  for (int i = 3; i <= n; i++)
  {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

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

Пространственная сложность: n. Используется массив размера n + 1, постоянные значения при расчёте сложнос��ей не учитываются.

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