动态规划

动态规划算法的主要思想

将原始问题划分成一系列子问题

求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间

自底向上地计算

---

动态规划算法的特点

利用空间换时间

---

使用Dynamic Programming的条件

–Optimal substructure（优化子结构）

当一个问题的优化解包含了子问题的优化解时，我们说这个问题具有优化子结构。

缩小子问题集合，只需那些优化问题中包含的子问题，减低实现复杂性

优化子结构使得我们能自下而上地完成求解过程

–Subteties（重叠子问题）

在问题的求解过程中，很多子问题的解将被多次使用

---

Dynamic Programming的实例

最短路径问题

最短路径问题

动态规划的求解过程：

1.划分求d(S,T)问题为三个子问题

从S到T的最短路径长度为：

d(S,T)=min{1+d(A,T), 2+d(B,T), 5+d(C,T)}

2.划分d(A,T)、d(B,T)、d(C,T)为6个子问题

3.求解最小子问题

d(A,T)=min{4+d(D,T), 11+d(E,T)}=min{22,12}=12

d(B,T)=min{9+d(D,T), 5+d(E,T),16+d(F,T)}=min{27, 6, 18}=6

d(C,T)=min{2+d(F,T)}=4

d(A,T)=22,d(B,T)=6,d(C,T)=4

4.最后确定从S到T的最短路径

d(S,T)=min{1+d(A,T), 2+d(B,T),5+d(C,T)}=min{23, 8, 9}=8

动态规划算法的设计步骤：

–分析优化解的结构：划分子问题、优化子结构、子问题重叠性

–递归地定义最优解的代价

d(S,T)=min{1+d(A,T), 2+d(B,T), 5+d(C,T)}

–递归地划分问题，直至不可划分

–自底向上求解各个子问题：

•计算优化解代价并保存之

•获取构造最优解的信息

–根据构造最优解的信息构造优化解