动态规划算法(分治算法和动态规划有什么不同和联系)

一、分治法与动态规划主要共同点：

1）二者都要求原问题具有最优子结构性质，都是将原问题分而治之，分解成若干个规模较小(小到很容易解决的程序)的子问题。然后将子问题的解合并，形成原问题的解。

二、分治法与动态规划实现方法：

① 分治法通常利用递归求解。

② 动态规划通常利用迭代法自底向上求解，但也能用具有记忆功能的递归法自顶向下求解。

三、分治法与动态规划主要区别：

① 分治法将分解后的子问题看成相互独立的。

② 动态规划将分解后的子问题理解为相互间有联系，有重叠部分。