剑指offer 斐波那契数列

Posted on |

斐波那契数列

题目

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

方法

从下向上计算，先根据f(0)和f(1)计算f(2),再根据f(1)和f(2)计算f(3),…

1
2
3
4
5
6
f(0)=0
f(1)=1
f(2)=f(0)+f(1)
f(3)=f(1)+f(2)
....
f(n)=f(n-2)+(n-1)

时间复杂度：O(n)
空间负责度：O(n)

方法1：自底向上的动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n==0:
            return 0
        elif n==1:
            return 1

        dp=[-1]*(n+1)
        dp[0],dp[1]=0,1

        for i in range(2,n+1):
            dp[i]=dp[i-1]+dp[i-2]
        return dp[n]

无效方法

效率很低，很多计算都是重复的。

1
2
3
4
5
6
7
8
9
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n==0:
            return 0
        if n==1:
            return 1
        return self.Fibonacci(n-1)+self.Fibonacci(n-2)

相似问题

剑指offer 跳台阶
剑指offer 变态跳台阶
矩形覆盖问题