Считайте способы добраться до N-й лестницы | Сет-2
Есть N ступенек, человек, стоящий внизу, хочет подняться наверх. Человек может подняться либо на 1 ступеньку, либо на 2 ступеньки за раз. Подсчитайте, сколько способов человек может достичь вершины.
Примеры:
Input: N = 1
Output: 1
Explanation: There is only one way to climb 1st stairInput: 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 = 3For 4th stair:
=> Number of ways to reach 3rd stair = prev1 + prev2. i.e. curr = 3 + 2 = 5.
=> prev2 = prev1 = 3. prev1 = curr = 5For 5th stair:
=> Number of ways to reach 3rd stair = prev1 + prev2. i.e. curr = 5 + 3 = 8.
=> prev2 = prev1 = 5. prev1 = curr = 8For 6th stair:
=> Number of ways to reach 3rd stair = prev1 + prev2. i.e. curr = 8 + 5 = 13.
=> prev2 = prev1 = 8. prev1 = curr = 13Below is the image representation of each step of above explanation:
Выполните шаги, указанные ниже, чтобы решить проблему:
- Объявите две переменные (скажем, prev1 и prev2 ) для хранения двух предыдущих состояний для любого текущего состояния и инициализируйте их количеством способов достижения 1-й и 2-й ступенек.
- Итерация от 3 -й ступени к N -й ступени:
- Рассчитайте количество способов добраться до текущей лестницы, как показано в приведенном выше наблюдении.
- Теперь обновите переменные prev1 и prev2 в соответствии с наблюдениями.
- Возвращает полученное в результате значение N -й ступеньки.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство : O(1)