本文共 1008 字，大约阅读时间需要 3 分钟。

题解一： 动态规划

按照斐波那契数列的数列定义写就行了

1.如果n=0,返回0即可。如果不单独考虑，那么给数组分配空间时会出错。 2定义长度为n+1的数组dp 3.初始化前两个值分别为0，1 4.对于索引i从2到n+1，建立循环： dp[i]=(dp[i-1]+dp[i-2]) % 1000000007

时间复杂度：O(n),一个循环所用的时间

空间复杂度：O(n),数组dp所占用的空间

python:

class Solution(object):    def fib(self, n):        """        :type n: int        :rtype: int        """        if n==0:           return 0        import numpy as np        dp=np.zeros(n+1,dtype=int)        dp[0]=0        dp[1]=1        for i in range(2,n+1):            dp[i]=(dp[i-1]+dp[i-2]) % 1000000007        return dp[n]

题解二：

动态规划，简化上一题解的空间复杂度

由于dp列表第i项只与第i-1项和第i-2项有关，因此只需初始化三个整型变量sum,a,b,利用辅助变量sum使a,b两数字交替前进即可。sum代表第i项值，a代表第i-1项值,b代表第i-2项值

时间复杂度：O(n),一个循环所用的时间

空间复杂度：O(1),变量sum,a,b所占用的常数空间 java:

class Solution {       public int fib(int n) {           int a=0,b=1,sum;        for(int i=0;i

python:

class Solution(object):    def fib(self, n):        """        :type n: int        :rtype: int        """        a,b=0,1        for _ in range(n):            a,b=b,a+b        return a%1000000007

转载地址：http://phrh.baihongyu.com/