# 简介
复杂问题分阶段简化成简单问题，就是动态规划的思想。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。 适合初学者用动画的方式来简单的理解什么是动态规划: 漫画解读：什么是动态规划？
# 动态规划是什么？
动态规划是算法设计中的一种方法。
它将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题。
# 1. 动态规划的三个关键点：
最优子结构（大问题拆成小问题）
边界（初始条件）
状态转移方程（用表达式表示）
# 2. 什么时候需要动态规划
- 重叠子问题
- 最优子结构
- 优化递归
# 3. 动态规划解题思路
- 核心思想是递推。
- 难点在于想清楚状态 dp[i] 代表什么，然后构造状态转移矩阵，利用初始条件递推出最终结果。
- 常用画表的方式记录小问题的结果，然后大问题再根据小问题的结果计算。
# 4. 无后效性
“未来与过去无关”，这就是无后效性。也就是说子问题已经计算出来的结果，不会受未来的因素而改变。