p.s.推荐一个动态规划的笔记：背包问题九讲，这里面对背包问题做了精炼的总结，适合对背包问题已经有一定学习心得的人看，入门的话，我是看《算法图解》和《算法导论》（但总之我的动态规划还是学的很烂。。。）
动态规划的基本思想是原问题视为一个基础问题不断扩大规模的结果，在求解过程中，规模更大的问题以某种方式依赖于已求解出的子问题。最经典的例子是01背包问题，而算法导论上给出的例子是钢管切割问题，即不同长度的钢管有着不同的收益（一般不是线性的依赖关系），需要寻找一种切分方式使得总收益最大化。
在用动态规划的思想求解时，需要确保子问题的最优解已被得到并保存，因此需要一定的空间复杂度，在01背包问题中，令物品的个数为n，背包容量为V，则背包容量未经优化的空间复杂度为O(nV)，考虑求解顺序后可以复用一个一维数组将复杂度优化到O(V)。
需要用动态规划求解的问题一般暴力求解的时间复杂度是O(2^n)，其暴力求解手段又一般是深度搜索，如果直接在暴力搜索上优化，一般是记忆化搜索+剪枝优化，其中记忆化搜索就相当于保存子问题的最优解，而剪枝则是根据边界条件做一些常数优化。所以动态规划相关问题的一个思路就是，先写出暴力深搜的版本，然后在此基础上引入额外的空间复杂度将时间复杂度从指数级减少到多项式级，最后再进行力所能及的剪枝优化。