Вправа з програмування – Підйом по сходах – Числа Фібоначчі – 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);
}
};
Примітка. Рекурсивна функція видасть TIME LIMIT EXCEEDED у тесті 44. Це тому, що рекурсивна функція зазвичай обчислює проміжні значення багато разів. Наприклад, , . обчислюється двічі.