分治法(divide-and-conquer)可能是最著名的通用算法设计技术了。许多非常有效的算法实际上就是这个通用算法的特殊实现。

动态规划(dynamic programming)与分治法 (divide and conquer) 相似,都是通过组合子问题的解来求解原问题。分治法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。与此相反,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题(子问题的求解是递归进行的,将其划分为更小的子子问题)。在这种情况下,分治算法会做许多不必要的工作,它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都要重新计算,避免了这种不必要的计算工作。

动态规划方法通常用来求解最优化问题(optimization problem)。这类问题可以有很多可行解,每个解都有一个值,我们希望寻找具有最优值(最小值或最大值)的解。我们称这样的解为问题的一个最优解(an optimal solution),而不是最优解(the optimal solution),因为可能有多个解都达到最优值。