动态规划
Those Who Cannot remember the past are condemned to repeat it
那些不能记住过去的注定重蹈覆辙
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远小于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解决一个给定问题，我们需要先解其不同部分（子问题），再根据子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决子问题一次，从而减少计算量：一旦某一个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题的解时可以直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
一言以蔽之
动态规划算法的核心就是记住已经解决过的子问题的解，从而节省接下来面对相同子问题的时间，这点尤其在重复的子问题数目很大的时候更明显；使用动态规划来解题只需要多项式时间复杂度。这也是开头图片所想要表达的观点，如果没有使用动态规划来仅解决子问题一次，那么每次重复性地解决相同的子问题就会变得毫无意义，像受处罚一样浪费时间。
动态规划的适用情况
- 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态規劃算法解决问题提供了重要线索。
- 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
- 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态規劃算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
