从斐波那契数列初探动态规划

• 2019 年 10 月 6 日
• 筆記

动态规划

1.规律

• 递归+记忆化 -> 递推(动态递推)
• 状态的定义：opt[n],dp[n],fib[n]
• 状态转移方程：opt[n]=best_of(opt[n-1],opt[n-2],…)
• 最优子结构

2.斐波那契数列

2.1 递归

f(n)=f(n-1)+f(n-2)

f(0)=0

f(1)=1

def fib(n):      return n if n<=1 else fib(n-1)+fib(n-2)  

复杂度分析

复杂度为2^n。时间复杂度为每次节点相加，虽然并非满二叉树，但是数量级上是2^n。

2.2 记忆化

那如何加速呢？(也就是记忆化。)

记忆化就是增加了缓存，如下所示：

def fib1(n,memory):      if n<=0:          return 0      elif n==1:          return 1      elif not memory[n]:          memory[n]=fib1(n-1,memory)+fib1(n-2,memory)      return memory[n]  n = 20  memory = [0]*(n+1)  print(fib1(n,memory))  

这样就把时间复杂度变为O(n)。

2.3 递推

上述写得像递归又不像递归，很别扭，然后我们将递归+记忆化，得到递推。

从叶子节点顺推上去，直接递推更加容易，于是得到这种解法。

def fib2(n,memory):      memory[0]=0      memory[1]=1      for i in range(n+1):          memory[i]=memory[i-1]+memory[i-2]      return memory[n]  memory = [0]*(n+1)  print(fib(20))  print(fib1(n,memory))  

上述递归+记忆化=>递推就是dp思想。

dp转移方程(状转移方程)就是：memory[i]=memory[i-1]+memory[i-2]。

这是一种非常简单的dp。平时要比这个复杂多。