mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 08:27:30 +08:00
54 lines
1.4 KiB
Markdown
Executable File
54 lines
1.4 KiB
Markdown
Executable File
# [509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)
|
||
|
||
|
||
## 题目
|
||
|
||
The **Fibonacci numbers**, commonly denoted `F(n)` form a sequence, called the **Fibonacci sequence**, such that each number is the sum of the two preceding ones, starting from `0` and `1`. That is,
|
||
|
||
F(0) = 0, F(1) = 1
|
||
F(N) = F(N - 1) + F(N - 2), for N > 1.
|
||
|
||
Given `N`, calculate `F(N)`.
|
||
|
||
**Example 1:**
|
||
|
||
Input: 2
|
||
Output: 1
|
||
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
|
||
|
||
**Example 2:**
|
||
|
||
Input: 3
|
||
Output: 2
|
||
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
|
||
|
||
**Example 3:**
|
||
|
||
Input: 4
|
||
Output: 3
|
||
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
|
||
|
||
**Note:**
|
||
|
||
0 ≤ `N` ≤ 30.
|
||
|
||
|
||
## 题目大意
|
||
|
||
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
|
||
|
||
```
|
||
F(0) = 0, F(1) = 1
|
||
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
|
||
```
|
||
|
||
给定 N，计算 F(N)。
|
||
|
||
提示：0 ≤ N ≤ 30
|
||
|
||
## 解题思路
|
||
|
||
|
||
- 求斐波那契数列
|
||
- 这一题解法很多，大的分类是四种，递归，记忆化搜索(dp)，矩阵快速幂，通项公式。其中记忆化搜索可以写 3 种方法，自底向上的，自顶向下的，优化空间复杂度版的。通项公式方法实质是求 a^b 这个还可以用快速幂优化时间复杂度到 O(log n) 。
|