斐波那切数列

发表于 | 分类于 | 次

###题目

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。（n<=39）

解题思路：

使用字典存储每次的结果。

###代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        return fib(n)
    
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 1
    tmp = {0:0, 1:1, 2:1}
    for i in range(3, n+1):
        tmp[i] = tmp[i-1] + tmp[i-2]
    return tmp[n]