Как решить проблему лестницы с помощью 5 строк JavaScript

Если вы новичок в алгоритмах и летткодах, то проблема с лестницей — просто пресловутая!

Что такое задача программирования «Лестница»?

Проще говоря….

Представьте себе лестницу с N ступенями. Если вы можете сделать 1, 2 или 3 шага за раз, сколькими различными способами вы можете добраться до верха лестницы?

Впервые столкнувшись с подобной задачей, вы наверняка испугаетесь. Даже сама по себе, как математическая задача, она очень трудна.

Есть несколько очевидных случаев. Вы можете сделать 1 шаг за раз, N раз. Если N кратно 2, вы можете сделать 2 шага, N/2 раз. Также, если N кратно 3, вы можете сделать 3 шага, N/3 раз.

И еще есть все, что находится между ними. 🤔

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

Рекурсия в помощь

Как и было обещано, вот решение в 5 строках кода JavaScript…

// N is total number of steps in the staircase
// stepTaken is a counter for steps taken in each combination
function steps(N, stepsTaken = 0) {

  if (stepsTaken === N) return 1;
  else if (stepsTaken > N) return 0;

  return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);
}

Опаньки! Что это значит?

* Не паникуйте и не расстраивайтесь, если приведенный выше код вас смутил. * Я долгое время боролся с рекурсией, когда впервые изучал ее на уроках информатики в старших классах. Это, конечно, сложно. * Но как только вы поймете ее, она откроет вам целый мир новых возможностей!

Давайте пройдемся по этому решению.

Если вы думаете просто скопировать приведенное выше решение и уйти, вы упускаете суть. Очень важно, чтобы вы понимали, что происходит.

функция steps(N, stepsTaken = 0) — это простой рекурсивный счетчик.

Давайте пройдемся по нему:

1. Мы находимся внизу лестницы, шагов не сделано. Поэтому stepsTaken = 0.
2. Перед вами 3 возможности: сделать 1 шаг, прыгнуть вверх на 2 ступеньки или прыгнуть вверх на 3 ступеньки.
3. Теперь нам нужно учесть ВСЕ 3 возможности. Итак, представьте, что вы клонируете лестницу и себя 2 раза. Кроме того, у каждого из вас есть своя версия переменной stepsTaken, которую вы носите с собой. Вы и ваши клоны проходите через одну из этих «дверей» (обратите внимание, что каждый из вас должен пройти через РАЗНУЮ дверь):

steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)

Как только вы пройдете через выбранную дверь, ваш индивидуальный счетчик stepsTaken будет увеличен на 1, 2 или 3 (в зависимости от того, через какую дверь вы прошли). После этого вы сразу же увидите еще 3 двери:

steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)

Опять же, вы будете клонировать себя 2 раза и каждый раз проходить через одну из этих шагов дверей. Ваш счетчик stepsTaken снова увеличится на 1, 2 или 3. Это будет повторяться до тех пор, пока :

  if (stepsTaken === N) return 1;
  else if (stepsTaken > N) return 0;

Если вы превысили stepsTaken > N, ваша комбинация шагов НЕ засчитывается в общее количество уникальных способов подняться по лестнице.

Однако, если (stepsTaken === N), то бинго 🤩 вы нашли законную комбинацию шагов для подъема по лестнице и вы возвращаете 1, чтобы добавить к подсчету способов подняться по лестнице.

1. Теперь вспомните, как мы считаем количество возможных комбинаций stepsTaken для достижения вершины лестницы из N ступеней, просто складывая все возможности:

return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);

Запомните каждое законное сочетание ступеней, где if (stepsTaken === N) return 1 и каждый раз, если путь не действителен (overstep), то возвращается 0 : else if (stepsTaken > N) return 0.

Некоторые из вас могут спросить: Хорошо, это элегантно, но не является ли это супер неэффективным с точки зрения временной сложности?

Да, это очень высокая временная сложность. Однако есть трюк, позволяющий значительно улучшить этот показатель ➡️ Как решить проблему лестницы в JavaScript с помощью мемоизации.

Надеюсь, это имеет смысл, комментируйте ниже, если у вас есть вопросы?

Если вам понравилась эта статья, пожалуйста, загляните в мой блог Indepth JavaScript, где вы найдете еще больше интересных материалов. 🤓