Вправа з програмування – Підйом по сходах – Числа Фібоначчі – 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);
    }
};

Примітка. Рекурсивна функція видасть TIME LIMIT EXCEEDED у тесті 44. Це тому, що рекурсивна функція зазвичай обчислює проміжні значення багато разів. Наприклад, , .  обчислюється двічі.