斐波那契数列

斐波那契数列

http://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3

分别用递归和动态规划求解
递归:
C++写的才能满足题目要求,python写的会超出时间限制

class Solution {
public:
    int Fibonacci(int n) {
        //递归解法
        if(n <= 0)
            return 0;
        if(n == 1 || n == 2)
            return 1;     
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
};

动态规划方式:
根据斐波拉契数列的关系便可找到规律,进而完成代码编写,即:F(0) = 0, F(1) = 1,F(N) = F(N-1) + F(N -2)

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        #动态规划法
        mylist = [0,1]
        if n <= 0:
            return mylist[0]
        if n == 1:
            return mylist[1]
        for i in range(2,n+1):
            mylist.append(mylist[i - 1] + mylist[i - 2])
        return mylist[n]
        #递归,运行超时
        #if n <= 0:
        #   return 0
        # if n == 1 or n == 2:
        #    return 1
        # return self.Fibonacci(n-1) + self.Fibonacci(n-2)
全部评论
你好,请问递归写法为什么第七行要有 n==2,我把这个删去程序运行报错。
点赞 回复 分享
发布于 2020-05-11 22:20

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务