- 1、题目描述:
-3、 设计思想:
-4、视频讲解链接B站视频讲解
-5、代码:
c++版本:
class Solution { public: int Fibonacci(int n) { if(n<=1) return n; //因为第0项等于0,第1项等于1 if(n == 2) return 1;//因为第2项等于1 return Fibonacci(n-1) + Fibonacci(n - 2);//斐波那契数列公式为:f[n] = f[n-1] + f[n-2] } };
Java版本:
public class Solution { public int Fibonacci1(int n) { if(n<=1) return n;//因为第0项等于0,第1项等于1 if(n == 2) return 1;//因为第2项等于1 return Fibonacci(n-1) + Fibonacci(n - 2);//斐波那契数列公式为:f[n] = f[n-1] + f[n-2], } public int Fibonacci(int n) { if(n <= 1) return n; int a = 0,b = 1; int temp = 0; for(int i = 2;i <= n;i ++){ temp = a + b; a = b; b = temp; } return temp; } }
Python版本:
# -*- coding:utf-8 -*- class Solution: def Fibonacci1(self, n): # write code here if n <= 1: return n;#因为第0项等于0,第1项等于1 if n == 2: return 1;#因为第2项等于1 return self.Fibonacci(n-1) + self.Fibonacci(n - 2);#斐波那契数列公式为:f[n] = f[n-1] + f[n-2] def Fibonacci(self, n): # write code here if n <= 1: return n dp = [0 for i in range(n+2)] dp[1] = 1 dp[2] = 1 for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]