动态规划
基础概念
动态规划主要由两个部分组成，约束条件和目标函数，目的是根据当前约束条件的限制，求解出目标函数的最值。解决的是组合优化问题。从广义上讲，组合优化问题是涉及从有限的一组对象中找到"最佳"对象的问题。“最佳”是通过给定的评估函数来测量的，该函数将对象映射到某个分数或者成本，目标是找到最高评估分数和最低成本的对象。组合优化往往涉及排序、分类、筛选等问题。
组合优化其实就是处理离散事件的最优编排、分组、次序或筛选等问题的优化方法。实际上就是从有限个离散状态中选取最好的状态。
算法设计步骤
- 根据问题建立数学模型，也就是将问题用数学符号进行表示；一般根据所给的问题，考虑所给问题的子问题，在范围上(比如本来要走到终点的路径数，现在就考虑不走到终点，而是考虑子问题为走到任意一点的路径数)。
- 将问题表示成多步判断，确定子问题的边界，每一步判断就对应一个子问题，子问题类型与原问题一样。
- 确定目标函数，以函数的最大最小为依据。
- 确定是否满足原则。
- 列出优化函数的递推方程和边界条件。(约束条件)
使用条件:优化原则
必要条件：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优的决策序列
DP和分治算法的区别
分治算法: 将问题划分成多个性质相同的子问题(每个子问题都跟原问题是相同的，只是范围不同)，递归求解，再组合求出原问题的解。
动态规划: 子问题是跟原问题有区别的，子问题是原问题之前的多种状态。表示的是之前的状态，之前的状态的子问题。
可以说，动态规划是对分治递归的优化，存储求解过程中子问题的解，避免重复计算子问题来提高效率。