Считайте способы добраться до N-й лестницы | Сет-2

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

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

Примеры:

Input: N = 1
Output: 1
Explanation: There is only one way to climb 1st stair

Input: N= 2
Output: 2
Explanation: There are two ways and the sequence to climb to Nth stair are: (1, 2), (2)

Input: N = 4
Output: 5
Explanation: There are five possible ways and the sequence to climb to Nth stair are:
(1, 2, 3, 4), (1, 2, 4), (2, 3, 4), (1, 3, 4), (2, 4) 

Динамическое программирование и скользящее окно, а также некоторые другие подходы обсуждаются в Set-1 этой задачи. Но этот подход будет иметь лучшее общее вспомогательное пространство.

Подход: Эта проблема может быть решена с большей пространственной сложностью на основе следующего наблюдения:

If observed closely, the value of current state ( i ) depends on two states: the value of the previous state (i – 1) and the value of (i – 2) state.
Instead of using extra space only two variables can be used to store the values of the above-mentioned two states.
As one can either climb one step or two step at a time, so ith state value is the summation of the values of (i – 1)th and (i – 2)th state.

Следуйте приведенной ниже иллюстрации для лучшего понимания.

Иллюстрация:

Initially, There are one ways to reach 1st stair and the sequence to climb to 1st stair is: (1)
There are two ways to reach 2nd stair and the sequence to climb to 2nd stair are: (1, 2), (2)

For 3rd stair:
        => Number of ways to reach 3rd stair = prev1 + prev2. i.e. curr = 2 + 1 = 3.
        => prev2 = prev1 = 2. prev1 = curr = 3

For 4th stair:
        => Number of ways to reach 3rd stair = prev1 + prev2. i.e. curr = 3 + 2 = 5.
        => prev2 = prev1 = 3. prev1 = curr = 5

For 5th stair:
        => Number of ways to reach 3rd stair = prev1 + prev2. i.e. curr = 5 + 3 = 8.
        => prev2 = prev1 = 5. prev1 = curr = 8

For 6th stair:
        => Number of ways to reach 3rd stair = prev1 + prev2. i.e. curr = 8 + 5 = 13.
        => prev2 = prev1 = 8. prev1 = curr = 13

Below is the image representation of each step of above explanation:

 

Выполните шаги, указанные ниже, чтобы решить проблему:

  • Объявите две переменные (скажем, prev1 и prev2 ) для хранения двух предыдущих состояний для любого текущего состояния и инициализируйте их количеством способов достижения 1-й и 2-й ступенек.
  • Итерация от 3 -й ступени к N -й ступени:
    • Рассчитайте количество способов добраться до текущей лестницы, как показано в приведенном выше наблюдении.
    • Теперь обновите переменные prev1 и prev2 в соответствии с наблюдениями.
  • Возвращает полученное в результате значение N -й ступеньки.

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

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

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