Dynamic Program
Dynamic Program 动态规划
什么是动态规划？
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、电脑科学、经济学和生物资讯学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
可以用动态规划的问题特点：
- 求解过程是多阶段决策过程，每步处理一个子问题，可用于求解组合优化问题。
- 适用条件：问题要满足优化原则或最优子结构性质，即：一个最优决策序列的任何子序列本身，一定是相对于子序列的初始和结束状态的最优决策序列。
动态规划设计要素
- 问题建模，优化的目标函数是什么？约束条件是什么？
- 如何划分子问题（边界）？
- 问题的优化函数值与子问题的优化函数值存在着什么依赖关系？（递推方程）
- 是否满足优化原则？
- 最小子问题怎样界定？其优化函数值，即初始值等于什么？