动态规划之记忆的作用
动态规划(Dynamic&Programming)算法由20世纪50年代初美国数学家RE.Bellman创立，一般用于求解优化问题，问题中常见的词有最大、最小、最重、最长等等。
动态规划是一种高效地穷举算法，通过特定的数据结构设计达到高效的效果。为了方便理解，可以把动态规划分为三个关键字：
递归+记忆+猜测
其中猜测用来构造递归，记忆用来实现递归
一.动态规划算法求解步骤
1. 定义子问题。子问题与原问题的区别在于输入数据的规模不同。
2. 建立子问题之间的关系。一般是递归关系。
(1) 猜测(类似于递归和分治算法中的不妨设),启动求解过程;
(2) 子问题的解—>节点，子问题求解过程—>节点遍历，而节点的遍历需要满足拓扑排序。所谓拓扑排序简单来说就是：当前节点只与已求得值的节点有关；
3. 明确边界条件。
4. 得到原问题的解。一般在表上遍历得到(自底向上)。
5. 分析算法时间复杂度。T(n)=子问题个数x每一个子问题的时间
二.记忆的作用
我们通过再遇斐波那契数来说明动态规划中记忆的作用
斐波那契数：0 1 1 2 3 5 8...从第2项开始，后一个数的值等于前两个数之和
Input：输入一个整数n，
Output：输出斐波那契数列的第n项
递推方程如下所示：
算法1：常用的递归算法实现
# 一般的递归
def fib_rec(n):
if n <= 1: # 边界条件
f = n
else:
f = fib_rec(n - 1) + fib_rec(n - 2) # 递归调用
return f采用递归的时间复杂度为O(2^n),空间复杂度为O(n),虽然递归方法代码简洁，容易理解，但是效率很低，且有大量的重复计算。
算法2：动态规划
利用记忆提高实现效率
如上图所示，在展开递归树时，将已经求出的值存储在一张额外的表中(此处的表即为特定的数据结构)，下一次展开计算时，先查看表中是否已经有记录，如果有，则直接取用，不用展开，如果没有，则重复上一步。
实现1：自上而下
# 动态规划：自上而下的实现
memo = {} # 存储结果的字典
def fib_top_down(n):
if n in memo: # 查表
return memo[n]
else:
if n <= 1:
f = n
else:
f = fib_top_down(n - 1) + fib_top_down(n - 2) # 递归调用
memo[n] = f # 自上而下填表
return f
由于没有重复计算，每个节点只展开一次，所以算法时间复杂度T(n)=O(n)
实现2：自底向上
此外，还有一种更高效的动态规划实现方法，即自底向上，不用递归，而是用循环实现
# 动态规划：自底向上的实现
def fib_bottom_up(n):
fib = {} # 存储结果的字典
for k in range(n + 1):
if k <= 1: # 边界条件
f = n
else:
f = fib[k - 1] + fib[k - 2] # 自底向上填表
fib[k] = f
return fib[n]
时间复杂度同样为O(n)，但是没有用到递归调用(注意：代码中fib是字典而不是函数)。自底向上的实现方法更为常用。
END
往期回顾