剑指offer面试题09----斐波拉契数列

题目：大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项。n<=39

思路：
已知斐波那契数列的形式为0 1 1 2 3 5 8 ...，因此可以知道，对于n小于2时分别表示0 1，当n>=2时，f(x) = f(x-1)+f(x-2) ，因此比较容易想到使用递归，不过递归的复杂度比较高，使用动态规划能更好的节省时间，即将数列每一位的元素保存起来，后边位的数据直接调用前边的结果。

Python代码如下：

class Solution(object):
    def fib_recru(self,n):
        '''
        递归方法，思路简单，但是不能通过在线测试，
        因为复杂度高，做了很多重复运算
        '''
        if n==0:
            return 0
        elif n==1:
            return 1
        else:
            return self.fib_recru(n-1)+self.fib_recru(n-2)

   def fib_dp(self,n):
    '''
        动态规划方法，依次保存前面的结果，复杂度低
    '''
    dp = [0, 1, 1]

    for index in range(3, n + 1):
        dp.append(0)
        dp[index] = dp[index - 1] + dp[index - 2]

    return dp[n]

s = Solution()
print s.fib_recru(5)
print s.fib_dp(5)