Выведите все способы добраться до N-й лестницы с прыжком на 1 или 2 единицы за раз
Даны положительное целое число 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:
- Perform the two jumps of 1 unit each as 1 -> 1.
- 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)