0509. 斐波那契数

# 0509. 斐波那契数#

• 标签：数组
• 难度：简单

## 题目大意 #

• 斐波那契数列的定义如下：
• $f(0) = 0, f(1) = 1$。
• $f(n) = f(n - 1) + f(n - 2)$，其中 $n > 1$。
• $0 \le n \le 30$。

• 示例 1：
 1 2 3  输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 
• 示例 2：
 1 2 3  输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 

## 解题思路 #

### 思路 1：递归算法 #

1. 写出递推公式：$f(n) = f(n - 1) + f(n - 2)$。
2. 明确终止条件：$f(0) = 0, f(1) = 1$。
3. 翻译为递归代码：
1. 定义递归函数：fib(self, n) 表示输入参数为问题的规模 $n$，返回结果为第 $n$ 个斐波那契数。
2. 书写递归主体：return self.fib(n - 1) + self.fib(n - 2)
3. 明确递归终止条件：
1. if n == 0: return 0
2. if n == 1: return 1

### 思路 1：代码 #

 1 2 3 4 5 6 7  class Solution: def fib(self, n: int) -> int: if n == 0: return 0 if n == 1: return 1 return self.fib(n - 1) + self.fib(n - 2) 

### 思路 2：代码 #

  1 2 3 4 5 6 7 8 9 10 11 12  class Solution: def fib(self, n: int) -> int: if n <= 1: return n dp = [0 for _ in range(n + 1)] dp = 0 dp = 1 for i in range(2, n + 1): dp[i] = dp[i - 2] + dp[i - 1] return dp[n] 

### 思路 2：复杂度分析 #

• 时间复杂度：$O(n)$。一重循环遍历的时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$。用到了一维数组保存状态，所以总体空间复杂度为 $O(n)$。因为 $dp[i]$ 的状态只依赖于 $dp[i - 1]$ 和 $dp[i - 2]$，所以可以使用 $3$ 个变量来分别表示 $dp[i]$、$dp[i - 1]$、$dp[i - 2]$，从而将空间复杂度优化到 $O(1)$。
{"ft_lang_label":"__label__zh","ft_lang_prob":0.9205792,"math_prob":1.0000058,"size":1247,"snap":"2023-14-2023-23","text_gpt3_token_len":1015,"char_repetition_ratio":0.12228479,"word_repetition_ratio":0.07522124,"special_character_ratio":0.5028067,"punctuation_ratio":0.05952381,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99984264,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-04-01T17:31:45Z\",\"WARC-Record-ID\":\"<urn:uuid:9553f027-8b26-4ba6-9811-53d915569970>\",\"Content-Length\":\"231839\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d35994fa-4a24-46cb-a719-5e209d8e5ef5>\",\"WARC-Concurrent-To\":\"<urn:uuid:07958c1a-72e2-4040-803b-26e27736ae05>\",\"WARC-IP-Address\":\"113.1.0.117\",\"WARC-Target-URI\":\"https://algo.itcharge.cn/Solutions/0500-0599/fibonacci-number/\",\"WARC-Payload-Digest\":\"sha1:APVPF2RXTYA7FXZ6ZQJ2F5L7JNYQRKJK\",\"WARC-Block-Digest\":\"sha1:BDZ272VZYG4INAQQEJPIQSV62OIJB3HV\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-14/CC-MAIN-2023-14_segments_1679296950110.72_warc_CC-MAIN-20230401160259-20230401190259-00040.warc.gz\"}"}