简述动态规划法与分治法的异同

动态规划法和分治法都是常用的算法设计思想，它们可以解决许多计算问题，两者的异同点如下：

相同点：

1. 都是通过将复杂问题分解成若干个简单子问题来求解的。

2. 都是将子问题的解进行组合得到原问题的解。

3. 都需要具有最优子结构性质。

不同点：

1. 动态规划法通常用于求解最优化问题，而分治法通常用于求解搜索问题或者排序问题。

2. 动态规划法通常需要用到一个数组来存储中间状态，而分治法通常不需要。

3. 动态规划法通常是自底向上地解决问题，而分治法通常是自顶向下地解决问题。

4. 动态规划法通常需要进行状态转移，而分治法通常不需要。

总的来说，动态规划法和分治法都是非常重要的算法设计思想，它们都有自己的应用领域和优缺点，需要根据具体问题来选择合适的算法。