算法设计策略----动态规划法

动态规划法：与贪心法类似，动态规划法也是一种求解最优化问题的算法设计策略。它也采取分布决策的方法。但与贪心法不同的是，动态规划法每一步决策依赖子问题的解。直观上，为了在某一步做出决策，需要先求若干子问题，这就使得动态规划法是自底向上的。

按照多部决策方法，一个问题的活动过程可以分成若干阶段，每个阶段可能包含一个或多个状态。多部决策求解方法就是从初始状态开始做出每个阶段的决策，形成一个决策序列，该决策序列也成为策略。对于每一个决策序列，可以用一个数值函数（目标函数）衡量该策略的优劣。问题求解的目标是获取最优决策序列（最优策略）。

动态规划法基本要素：

最优子结构特性：和贪心法相同。

重叠子问题：动态规划法的子问题往往是重叠的，如果采用与分治法类似的直接递归会非常费时。为了避免重复计算，动态规划法一般采用自底向上的方式进行计算，并保存已经求解的子问题的值。当这些子最优解值被重复引用时，无需重新计算。

设计动态规划法步骤：

1. 刻画最优解的结构特性；
2. 递归定义最优解值；
3. 自底向上方式计算最优解值；
4. 根据计算得到的信息构造一个最优解。

相关算法：

• 多段图问题
• 关键路径问题
• Floyd(弗洛伊德）算法
• 最长公共子序列问题
• 0/1背包问题