Выведите все способы добраться до N-й лестницы с прыжком на 1 или 2 единицы за раз

Опубликовано: 21 Сентября, 2022

Даны положительное целое число N , представляющее N ступеней, и человек на первой ступеньке. Задача состоит в том, чтобы вывести все способы добраться до N ступеньки с прыжком на 1 или 2 единицы за раз.

Примеры:

Input: N = 3
Output: 
11
2
Explanation:
Nth stairs can be reached in the following ways with the jumps of 1 or 2 units each as:

  1. Perform the two jumps of 1 unit each as 1 -> 1.
  2. Perform the two jumps of 1 unit each as 2.

Input: N = 5
Output:
1111
112
121
211
22

Подход: Данную проблему можно решить с помощью рекурсии. Идея состоит в том, чтобы охватить оба случая одного или двух прыжков за раз по каждому индексу и вывести все возможные способы добраться до N ступеньки . Выполните следующие шаги, чтобы решить данную проблему:

  • Определите рекурсивную функцию, скажем, totalPossibleJumps(int N) , которая возвращает все возможные способы прыжков для достижения N ступеньки .
    • В начальной точке рекурсии проверьте базовые случаи как:
      • Если N < 0 , то это недопустимый способ. Итак, верните пустой массив
      • Если N = 0 , то это допустимый способ. Поэтому верните массив размера 1 , содержащий пустое пространство.
    • Вызывайте рекурсивную функцию два раза при каждом рекурсивном вызове, один для прыжка на 1 единицу, а другой для прыжка на 2 единицы и сохраняйте результаты отдельно.
    • Инициализируйте массив строк, скажем, totalJumps , чтобы хранить способы достижения i -го индекса и хранить все возможные способы достижения индекса i с результатами, сохраненными в двух приведенных выше рекурсивных вызовах.
  • После выполнения вышеуказанных шагов выведите все возможные комбинации, возвращаемые указанными выше рекурсивными вызовами, как totalPossibleJumps(N) .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(2 N )
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ