【剑指offer】裴波那契数列（Python）

动态规划是“自下而上”求解，从最基础的base解到最终解。
这里基础解就是第0项和第1项，第2项=第0项+第1项，从第2项开始往上。
时间复杂度：O（n）
空间复杂度：O（1）

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        # 动规是从下往上的
        if n <= 1: return n
        pre1 = 1
        pre2 = 0
        fib = 0
        for i in range(2,n+1):
            fib = pre1 + pre2
            pre2 = pre1 
            pre1 = fib
        return fib