动态规划

将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

动态规划与分治法的区别

共同点

二者都是要求原问题具有最优子结构的特征，都是将原问题分而治之，分解成若干个规模较小的子问题，然后将子问题的解合并，形成原问题的解。

实现方法

• 分治法常常利用递归来实现。
• 动态规划通常利用迭代法自底向上求解，但也可使用具有记忆功能的递归法自顶向下求解。

区别

• 分治法将分解后的子问题看成是相互独立的；
• 动态规划将分解后的子问题理解为相互间是有联系的，有重叠部分的。