Подсчёт количества вариантов подъёма по лестнице

Условие

Необходимо достичь вершины лестницы, содержащей n ступеней. За один шаг разрешено подняться либо на одну, либо на две ступени. Требуется определить, сколькими различными последовательностями шагов можно добраться до последней ступени.

Пример 1: Input: n = 2 Output: 2 Варианты: 1 шаг + 1 шаг, 2 шага

Пример 2: Input: n = 3 Output: 3 Варианты: 1 + 1 + 1, 1 + 2, 2 + 1

class Solution {
    public int climbStairs(int steps) {
        // реализация
    }
}

Ответ

Число способов удовлетворяет ways(n) = ways(n−1) + ways(n−2): последний шаг пришёл с одной из двух предыдущих ступеней. Достаточно хранить два предыдущих значения.

public int climbStairs(int steps) {
    if (steps < 0) throw new IllegalArgumentException();
    if (steps <= 1) return 1;
    int previous = 1, current = 1;
    for (int i = 2; i <= steps; i++) {
        int next = Math.addExact(previous, current);
        previous = current;
        current = next;
    }
    return current;
}

Для нуля принят один способ — не делать шагов. Время O(n), память O(1). Ответ превышает int начиная с 46 ступеней; Math.addExact сообщит об этом вместо тихого переполнения. Для больших n нужен BigInteger и соответствующий возвращаемый тип.