- 动态规划是一种常用的优化算法的技术，是一种解决最优解问题的方法。
- 由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。
- 这篇文章主要总结我个人在做各种类型DP问题中DP数组的建立方法、一些基本思想以及一些常见的DP的优化技巧。
概念
- 动态规划(Dynamic Programming)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
- 能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
- 一个问题的最优解包含其子问题的最优解，这个性质被称为最优子结构性质。
- 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次(overlap problem)，这种性质称为子问题的重叠性质。
- 已经求解的子问题，不会再受到后续决策的影响，这个性质被称为无后效性行性质。
动态规划解题五步曲
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组