一、斐波那契数简介

斐波那契数是数学上的一种数列，它的排列是：1，1，2，3，5，8，13，21，34，55，89，144… 第一项和第二项为1，从第三项开始，每项等于前面两项之和

二、暴力求解

1、分析

已知条件

$a_1=1$
$a_2=1$
$a_n=a_{n-1}+a_{n-2} \ (n>2)$

2、求解分析

从已知条件中惊奇的发现：呀，这不简单吗？初始条件有了，通向公式有了，那我从 $a_3$ 开始使用递归不就解决了吗？赶紧试一试代码,求解 $a_{30}$

3、代码实现：

import time
def Fibonacci(n):
    if n < 3:
        return 1
    return Fibonacci(n - 2) + Fibonacci(n - 1)
start=time.time()
result=Fibonacci(30)
end=time.time()
print('结果：{0} 耗时：{1}'.format(result,(end-start)))
#输出
结果：832040 耗时：0.6922831535339355

4、复杂度分析

使用递归，其计算图如下

图片来源参考链接

可以将其看做一颗二叉树，每个节点就是一个计算单元，根据一颗满二叉树节点数与深度的关系 $节点数=2^{深度-1}$ ，时间福复杂度可以近似为 $O(2^n)$ ,空间复杂度为 $O(n)$

三、时间复杂度优化

上面递归的方式在于每次都需要大量重复计算想同的节点，如下图

image.png
那么换一个角度，重复的节点只计算一次，这样时间上是不是就少很多呢，开始编码，自底向上，从一直计算到,并使用数组存储计算过程的结果

import time
import numpy as np
def Fibonacci(n):
    array = np.zeros(n)
    array[0] = 1
    array[1] = 1
    for i in range(2, n):
        array[i] = array[i - 1] + array[i - 2]
    return array[n - 1]
start=time.time()
result=Fibonacci(30)
end=time.time()
print('结果：{0} 耗时：{1}'.format(result,(end-start)))
#输出
结果：832040.0 耗时：0.0

奇迹发生了，时间从上面的0.69变成了0.0，完全是一个飞跃，此时，时间福复杂度为 $O(n)$ ,空间复杂度为 $O(n)$ 。但是还有个问题：是不是忘记了已知条件：

$a_n=a_{n-1}+a_{n-2} \ (n>2)$

第n个值只和前面的两个值有关，也就是说可以两个内存单元就解决的事情，为啥要存储n个呢？于是进行在优化...

四、空间复杂度优化

目标数只依赖于前面俩个数，再之前的数根本不需要浪费前面 $n-3,n-4$ 等空间

def Fibonacci(n):
  if n<3:
    return 1
  a,b=1,1
  c=0
  for i in range(2,n):
    c=a+b
    a=b
    b=c
  return c

使用三个变量，时间福复杂度为 $O(n)$ ,空间复杂度为 $O(1)$ ，彻底完成了从时间到空间上的优化。

五、动态规划

1、优化总结

从Fibonacci数的计算优化过程中，从数列的初始条件和通项公式，一步步的优化时间和空间复杂度，但是核心都围绕着一个通项公式来计算，这个通向公式就叫做状态转移方程，可以理解为解决问题的关键规律；初始项叫做边界条件，是大问题的最小子问题；动态规划的思路总体而言还是问题的拆分，将 $a_n拆解为a_{n-1},a_{n-2}$ ，这一步的思考是解决的问题的突破口，叫最优子问题，根据突破口一步一步的拆分，直到拆分到边界条件，这样就完成解决问题的思路，后面就是求解优化的问题。