Упражнение по кодированию — Восхождение по лестнице — Числа Фибоначчи — C++ — Онлайн-судья

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

Описание проблемы: http://oj.leetcode.com/problems/climbing-stairs/

На первый взгляд эта задача может показаться сложной, но если вы на секунду задумаетесь, она может оказаться такой простой. Ответ — Числа Фибоначчи (см. здесь, здесь )

Ну, исходные числа Фибоначчи определяются как последовательности:

Для этой задачи нам просто нужно немного изменить:

и поскольку только для 1 шага есть только 1 отличный способ, а для 2 шагов у нас есть два решения: 1 + 1 или 2.

Остальное в виде ряда Фибоначчи. Потому что из текущей позиции мы, возможно, из двух предыдущих позиций, F(n-1) и F(n-2).

Вы можете использовать рекурсию, но это можно решить с помощью более эффективного итеративного решения.

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        // f(n) = f(n - 1) + f(n - 2)
        int a = 1, b = 2, c = a + b;
        for (int i = 3; i <= n; i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

Или вы предпочитаете более простую рекурсивную функцию:

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

Примечание. Рекурсивная  функция даст ПРЕВЫШЕНИЕ ВРЕМЕНИ на тесте 44. Это связано с тем, что рекурсивная функция обычно вычисляет промежуточные значения много раз. Например, , .  вычисляется дважды.