Сложность: easy
Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).
Пример:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
👨💻 Алгоритм:
1⃣Проверка начального условия
Если N <= 1, вернуть N.
2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.
3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.
😎 Решение:
class Solution:
def fib(self, N: int) -> int:
if N <= 1:
return N
current, prev1, prev2 = 0, 1, 0
for _ in range(2, N + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return current
Ставь 👍 и забирай 📚 Базу знаний