题解 | #斐波那契数列#

法一：记忆化搜索。直接根据定义递归存在很多重复计算，时间复杂度太高。用记忆化搜索计算过的保存下来。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        fib=[0]*n
        fib[0]=1
        fib[1]=1
        for i in range(2,n):
            fib[i]=fib[i-1]+fib[i-2]
        return fib[n-1]        

法二：利用辅助变量cusum，交替更新a，b。

class Solution:
    def Fibonacci(self , n: int) -> int:
        if n<=2:
            return 1
        else:
            a=1
            b=1
            for i in range(n-2):
                cusum=a+b#直接求和
                a=b#更新a
                b=cusum#更新b
            return cusum

属于动态规划？设置边界条件和状态转移方程。。。