题解 | #斐波那契数列#

关于这道题，咱们就直接说说动态规划的解法，首先题目非常贴心给出了递推方程，所以得知n<3时，直接返回1就可以了这样就有了边界。

接下来讨论n>=3的情况，假设，所有斐波那契数列按从左到右一条直线排序，也即1、1、2、3、5、8、13....

由公式知道，前两个斐波那契数之和=第三个斐波那契数，如何求得第n个斐波那契数呢，就由题目中给出的递推方程来递推，假设a,b代表最初两个数，则c = a+b,也就是求得1，1，2， 接下来再求1，2，3. 我们可以观察到，自始自终只需要三个变量就够了，不需要数组去存储每一个斐波那契数，每次循环后，只需要做以下操作就可以

c = a + b
a, b = b, c

这段代码的意思就是说，当求得c以后，对于下一个数来说，a变成了b，b变成了c。具体可以这么理解，有个大小为3的窗口在

斐波那契数列上滑动，每次向右滑动一格，每次滑动后，窗口1、2、3的值都会更新（1,2,3对应代码a，b，c），由于最开始的值已经得知，所以对于第n个斐波那契数，只需要滑动n-2次

from re import A
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n < 3 :
            return 1
        a, b, c = 1, 1, 0

        for i in range(n-2):
            c = a + b
            a, b = b, c
        return c