Climbing Stairs

Условие

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

Примеры

Input: n = 2

Output: 2

Explanation: Существует два способа: 1 + 1 и 2.

Input: n = 3

Output: 3

Explanation: Существует три способа: 1 + 1 + 1, 1 + 2 и 2 + 1.

Решение

fun climbStairs(n: Int): Int {
    if (n <= 2) return n // Если ступенек 1 или 2, то количество способов равно самому n

    var prev = 1 // Количество способов добраться до 1-й ступеньки
    var curr = 2 // Количество способов добраться до 2-й ступеньки
    
    // Используем динамическое программирование для нахождения решения
    for (i in 3..n) { // C 3 ступеньки и выше
        val next = prev + curr // Количество способов добраться до i-й ступеньки — сумма предыдущих двух
        prev = curr // Обновляем количество способов для i-1
        curr = next // Обновляем количество способов для i
    }

    return curr // Возвращаем количество способов добраться до n-й ступеньки
}

Временная сложность

O(n), где n — количество ступенек. Мы проходим по каждой ступеньке один раз.

Пространственная сложность

O(1), так как используется только несколько переменных для хранения предыдущих значений.