牛客网题库：https://www.nowcoder.com/exam/oj?questionJobId=10&subTabName=online_coding_page

动态规划BM62：

题目如下：

Python实现代码如下：

1）递归实现

#
# @param n int整型
# @return int整型
#
# 递归方法
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n <= 2:
            return 1
        else:
            return self.Fibonacci(n - 2) + self.Fibonacci(n - 1)


s = Solution()
print(s.Fibonacci(10))

解题思路：

        1、递归结束条件（使用递归方法解题时，都需要先找出递归结束条件）：题目所示斐波那契数列从1开始，第一个位置、第二个位置均为1，是确定的；递归结束条件即为 if n <=2: return 1；

        2、若不满足递归结束条件，则需要走递归流程：题目所示n>2时，f(x) = f(x-2) + f(x-1)，即当前数值=前两个数值之和；f(x)为函数本身，因此不满足递归结束条件时，递归过程为 return self.Fibonacci(n - 2) + self.Fibonacci(n - 1)，其中self.Fibonacci()表示引用函数自身。

        递归方法实现，空间复杂度低O(1)，时间复杂度较高O(2ⁿ)‌，n较大时，递归方法循环次数过多，执行会超时。

2）数组实现

#
# @param n int整型
# @return int整型
#
# 数组方法
class Solution:
    def Fibonacci(self, n: int) -> int:
        f = [0 for i in range(n)]
        f[0], f[1] = 1, 1
        for i in range(2, n):
            f[i] = f[i - 2] + f[i - 1]
        return f[n - 1]


s = Solution()
print(s.Fibonacci(10))

解题思路：

        1、利用辅助数组，因题目要求输出斐波那契数列第n个数值，因此辅助数组长度设为n，数组中的值均初始化为0（也可以初始化为1，则第一个、第二个位置不用重新赋值）；

        2、辅助数组中第几个位置的值对应斐波那契数列第几个的数值，计算辅助数组中每个位置的值；

        3、第一个、第二个位置赋值为1；

        4、从第3个位置开始，依次计算数组后续第3->n个位置的值，每个位置的值等于前两个位置的值之和，即f[i] = f[i - 2] + f[i - 1]；

        5、循环结束后，辅助数组更新完成，返回数组最后一个位置的值即可。

        数组方法以空间换时间，辅助数组占用空间O(n)，时间复杂度O(n)，循环一次即可得出结果，极大提高了算法执行效率。

        实现斐波那契数列也可以有更优的方法，也可以不使用辅助数组，其他方法可拓展了解，此处暂不补充。