动态规划算法的主要思想
将原始问题划分成一系列子问题
求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间
自底向上地计算
动态规划算法的特点
利用空间换时间
使用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)}
–递归地划分问题，直至不可划分
–自底向上求解各个子问题：
•计算优化解代价并保存之
•获取构造最优解的信息
–根据构造最优解的信息构造优化解
