动态规划[dp]是解决问题很经典的算法。基本的思想，就是将一个问题转化为若干个子问题，当某个子问题的解已经算出来的时候，就将其记忆存储起来，以便于下次解决同一个子问题时就可以直接给出答案，这样的一个好处就是可以避免重复计算。动态规划适用于有重叠子问题和最优子结构性质的问题，通常能够达到把指数级的时间复杂度下降为多项式时间复杂度的效果。
需要注意的几个点：
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/u011000290/article/details/47398033