动态规划法(总述)多阶段决策最优化问题

动态规划: 研究最优控制问题提出的
该问题有n个输入，问题的解由这n个输入组成，这个子集必须满足事先给定的条件，这些条件称为约束条件，满足约束条件的可行解可能不只有一个为了衡量可行解的优劣，通常以一些函数的形式，这些标准函数是目标函数，使得目标函数取得极大值极小值的解称为最优解，最优化问题
多阶段决策过程满足最优性原理，在多阶段决策中，各个子问题解只于它前面的子问题相关，而且各个子问题解都是相对于当前状态的最优解，整个问题的最优解是各个子问题的最优解构成的。

6.1.2动态规划问题的设计思想
1划分子问题
将原问题分解为若干个子问题，每一个子问题对应一个决策阶段，并且子问题之间具有重叠关系
2.确定动态规划函数
根据子问题之间的重叠关系找到满足的递推关系式(动态规划函数)
3.填写表格
设计表格，以自底向上的方式计算各个子问题的解并填写表格，实现动态规划过程。

6.1.3简单的例子—数塔问题
6.2图问题的动态规划法
6.2.1多段图的最短路径问题
6.2.2多源点的最短路径问题 Floyd算法(典型的动态规划算法)
6.2.3TSP问题
6.3组合问题中的动态规划法
6.3.1最长递增子序列问题6
6.3.2最长公共子序列问题
6.3.3 0/1背包问题
6.4查找问题的动态规划法
6.4.1最优二叉查找树问题
6.4.2近似串皮皮匹配问题