动态规划不是一种具体的算法，而是一种算法思想：若要解决一个给定的问题，我们需要解其不同的部分（子问题），然后根据子问题的解，得出原问题的解。
应用这种算法思想解决问题的可行性，对子问题与原问题的关系，以及子问题和子问题之间的关系，这两方面都有一些要求，他们分别对应了最优子结构和重复子问题。
最优子结构
最优子结构规定的是子问题和原问题之间的关系。
动态规划要解决的都是一些问题的最优解，即从很多解决问题的方案中，找到最优的一个 。当我们在求一个问题最优解的时候，如果可以把这个问题分解成多个子问题，然后递归的找到每个问题的最优解，最后通过一定的数学方法，对各个子问题的最优解进行组合得出最终的结果。总结来说就是：**一个问题的最优解是由它的各个子问题的最优解决定的。**
将子问题的解进行组合可以得到原问题的解是动态规划可行性的关键。在解题中，一般使用动态转移方程来描述这种组合。
例如：原问题的解为`f(n)`，其中`f(n)`也叫做状态。状态转移方程`f(n) = f(n-1) + f(n-2)`
描述了一种原问题和子问题之间的关系。
重复子问题
重复子问题规定的是子问题与子问题之间的关系。
当我们在递归的寻找每个子问题的最优解的时候，有可能会重复的遇到一些更小的子问题，而且这些子问题会重复的出现在子问题里，出现这样的情况，会有很多的重复计算。动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候，动态规划可以减少很多的重复计算。
重复子问题不是保证解的正确性所必须的，但是如果递归求解子问题时，没有出现重复子问题，则没有必要使用动态规划，直接使用普通的递归就行。
例如：斐波拉契数列的状态转移方程`f(n) = f(n-1) + f(n-2)`。
- 在求
f(5)时，要求出子问题f(4)和f(3)的解，得到结果之后再组合成原问题f(5)的解。 - 在递归求
f(4)的时候，又要求出子问题f(3)和f(2)的解.
这里的求 f(3)和求f(5)时候的f(3)又重复了。
核心：就是找出子问题及其子问题与原问题之间的关系。
找到了子问题以及子问题与原问题之间的关系，就可以递归的求解子问题了。但是重叠的子问题使得递归会产生很多的重复计算。于是就想到了记忆化递归法：若能事先确定子问题的范围，就可以建表存储子问题的答案。
关键点总结：
- 证明问题的方案中包含一种选择，选择之后，留下一个或者多个子问题
- 设计子问题的递归描述方式
- 证明对原问题的最优解包括了对所有子问题的最优解
- 证明子问题是重叠的（这一步不是动态规划正确性所必须的具备的条件，但是如果子问题无重叠，则效率和一般的递归是相同的）
