LeetCode面试题10-一、斐波那契数列【剑指offer】【简单】【Python】【动态编程】问题写一个函数，输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列定义如下：F(0)=0,F(1)=1F(N)=F(N-1)+F(N-2)，其中N>1。斐波那契数列从0开始，1、后面的斐波那契数是前面两个数相加得到的。答案需要取模1e9+7(1000000007)。如果初始计算结果为：1000000008，请返回1。例1：输入：n=2输出：1例2：输入：n=5输出：5提示：0<=n<=100注：本题为与主站点上的问题509相同。idea动态规划fib(n)=fib(n-1)+fib(n-2)注意fib(n)会越界，所以最好：fib(n)%1000000007=(fib(n-1)%1000000007+fib(n-2)%1000000007)%1000000007但是因为Python中整数的大小限制取决于计算机的内存（可以理解为无穷大），所以大数越界的问题可以被忽略。时间复杂度：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_1返回dp_0%1000000007GitHublinkPython
