动态规划可解问题的特点
如果一个问题可以通过动态规划求解，则这个问题一定（充分不必要）满足这两个特点：
最优子结构
动态规划可以解决的问题通常是求问题最优解的问题。且这种问题可被分割为多个子问题，子问题的解也是最优的。通过各个子问题的最优解可以逐步计算出全局最优解，得出答案。
无后效性
动态规划划分出的子问题有以下性质：某个子问题的结果被求解之后，其值不会受如何求解影响。后面的计算如果可以用到这个子问题的结果，则和这个子问题通过怎样的方法怎样的顺序求解无关，即“未来和过去无关”。
动态规划的基本步骤
- 找子问题，把问题划分为各个阶段。
- 根据阶段划分确定动态规划的状态。
- 找到初始状态。
- 通过阶段之间的决策找出状态转移方程。
- 通过状态转移方程，通过递推或者记忆化搜索写出代码、优化，求出问题的解。
这些步骤看上去比较抽象，下面通过几个例题来熟悉一下这些步骤。
动态规划的时间复杂度分析
状态复杂度 乘以 转移复杂度。
例题
参考资料 && 拓展阅读 && 推荐题目
各种动态规划类型的介绍与题目举例：