LeetCode0509.斐波那契数列【简单】【Python】【动态编程】问题LeetCode斐波那契数列，通常表示为F(n)，形成一个数列，称为斐波那契数列，使得每个数都是前面两个的和，从0和1开始。即F(0)=0,F(1)=1F(N)=F(N-1)+F(N-2),forN>1.给定N，计算F(N)。示例1：输入：2输出：1解释：F(2)=F(1)+F(0)=1+0=1。示例2：输入：3输出：2解释：F(3)=F(2)+F(1)=1+1=2。示例3：输入：4输出：3解释：F(4)=F(3)+F(2)=2+1=3.注：0≤N≤30题侧重于斐波那契数列，通常用F(n)表示，形成的数列称为斐波那契数列。该序列以0和1开头，后面的每个数字都是前两个数字的总和。即：F(0)=0，F(1)=1F(N)=F(N-1)+F(N-2)，其中N>1。给定N，计算F(N)。示例1：输入：2输出：1解释：F(2)=F(1)+F(0)=1+0=1。示例2：输入：3输出：2解释：F(3)=F(2)+F(1)=1+1=2。示例3：输入：4输出：3解释：F(4)=F(3)+F(2)=2+1=3。提示：0≤N≤30思路解法1：递归fib(n)=fib(n-1)+fib(n-2)注意fib(n)会越界，所以最好：fib(n)%1000000007=(fib(n-1)%1000000007+fib(n-2)%1000000007)%1000000007但是，由于Python中整数的大小限制取决于计算机的内存（可以理解为无限），所以问题超出范围的大数字可以忽略。Python3代码类解决方案：deffib(self,n:int)->int:#解决方案一：递归ifn==0:return0ifn==1:return1return(self.fib(n-1)+self.fib(n-2))%1000000007方案二：动态规划时间复杂度：O(n)空间复杂度：O(1)Python3代码类方案：deffib(self,n:int)->int:#方案二：动态规划dp_0,dp_1=0,1for_inrange(n):dp_0,dp_1=dp_1,dp_0+dp_1returndp_0%1000000007GitHublinkPython
