从斐波那契数列初探动态规划
动态规划
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。平时要比这个复杂多。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-03-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
