Упражнение по кодированию — Восхождение по лестнице — Числа Фибоначчи — 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;
return climbStairs(n - 1) + climbStairs(n - 2);
}
};
Примечание. Рекурсивная функция даст ПРЕВЫШЕНИЕ ВРЕМЕНИ на тесте 44. Это связано с тем, что рекурсивная функция обычно вычисляет промежуточные значения много раз. Например, , . вычисляется дважды.