面试10：斐波那契数列

【题目描述】
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
【思路】
递归：超时
迭代：可行
【代码】

class Solution:
    def Fibonacci(self, n):
        # write code here
        '''def compute_Fibonacci(x):
            if x==0:
                return 0
            elif x==1:
                return 1
            else:
                return compute_Fibonacci(x-1)+compute_Fibonacci(x-2)
        return compute_Fibonacci(n)'''
        if n==0:
            return 0
        if n==1:
            return 1
        res = [0,1]
        for i in range(2,n+1):
            res.append(res[i-1]+res[i-2])
        return res[n]