文章目录
1.快速区分
动态规划是一种解决问题的策略。
线性规划是一类问题。目标函数为特定变量的线性函数，约束是这些变量的线性不等式（standard form）或等式（slack form），目的是求目标函数的最大值或最小值。线性规划和非线性规划在某些地方被称作静态规划，但未找到权威的参考文献。
2.动态规划（DP）
DP的两个重要性质：最优子结构（问题的最优解包含了其子问题的最优解）、重叠子问题（DP对每个子问题只求解一次，结果保存在表中，需要时直接查表。此性质减少了分解后需要计算子问题的数量--没有重复子问题，而分治法则需要计算遇到的所有子问题--含有重复的子问题，因而DP效率比分治法高）。
DP：分解为子问题，先解子问题，再得到原问题的解；子问题不相互独立
分治法（Divide and Conquer）：分解为子问题；子问题相互独立
备忘录法（memoization）：DP的变形。备忘录法的递归方式是自顶向下的，DP是自底向上的。
设计DP算法的一般步骤：
-找出最优解的性质，并刻画其结构特征；（最优子结构）
-递归地定义最优值；
-自底向上的计算最优值；
-根据计算过程中相关记录构造最优解（可选步骤）。
动态规划的应用：
-Floyd-Warshall算法：计算All-Pairs Shortest Paths；将边权值置为1，也可用于计算传递闭包。详见《算法导论》25.2
3.线性规划
4.参考文献
[1]Introduction to Algorithms（2nd Edition）
[2]http://bbs.csdn.net/topics/310248799
[3]http://ar.newsmth.net/thread-bbb7dde212bd73-1.html
[4]算法设计与分析