动态规划（Dynamic programming）通常用来解决最优化问题，在这类问题中，通过做出一组选择来达到最优解。在做出每个选择的同时，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题时，动态规划技术通常就会很有效，其关键技术就是对每个这样的子问题都保存其解，当重复出现时即可便重复求解。
动态规划与分治方法相似，都是通过组合子问题的解来求解原问题，分治法将问题划分为不相交的子问题，递归地求解子问题，再将它们组合起来求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。
实现方法
与朴素递归算法之所以效率很低，是因为它反复求解相同的子问题。因此，动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来，如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。因此，动态规划方法是通过额外的空间来换取时间，是典型的时空权衡（time-memory trade-off）的例子。并且时间上的节约可能是非常巨大的，可能将一个指数时间的解转化为一个多项式时间的解。动态规划有两种等价的实现方法，分别是带备忘的自顶向下法和自底向上法。
带备忘的自顶向下法(top-down with memoization)
此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中)。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是则直接返回保存的值，从而节省了计算时间，否则，按通常的方式计算这个子问题。
自底向上法(bottom-up method)
这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个大问题时，它所依赖的那些更小的子问题都已经求解完毕，结果已经保存。么个子问题只需求解一次，当我们求解它时，它所有的前提子问题都已经求解完成。
两种方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下的方法并未真正递归地考察所有可能的子问题。由于没有频繁递归函数调用的开销，自底向上方法的时间复杂度函数通常具有更小的系数。
子问题图
在思考一个动态规划问题时，应该弄清楚所涉及的子问题和子问题之间的依赖关系。问题的子问题图准确第表达了这些信息。它是一个有向图，每个顶点对应一个子问题，若求解子问题x的最优解时需要直接用到子问题y的最优解，那么在子问题图中就有一条从子问题x的顶点到子问题y的顶点的有向边。
自底向上的动态规划方法处理子问题图中顶点的顺序为：对于一个给定的子问题x，在求解它之前求解邻接到它的子问题y。即自底向上动态规划算法是按“逆拓扑序（reserve topological sort）”来处理子问题图中的顶点。类似，可以用“深度优先搜索”来描述自顶向下动态规划算法处理子问题的顺序。