分治法和动态规划的异同

分治法和动态规划是两种常见的算法设计策略，它们在解决复杂问题时有着相似之处，但也存在一些关键区别。

**分治法（Divide and Conquer）：**
1. **基本思想**：将一个大问题分解成若干个小的相同或相似子问题。
2. **步骤**：递归地解决子问题，然后合并子问题的结果得到原问题的解。
3. **典型例子**：排序算法（如快速排序、归并排序）、求解最大公约数等。

**动态规划（Dynamic Programming, DP）：**
1. **核心理念**：把原问题分解为相互重叠的子问题，并存储子问题的解，避免重复计算。
2. **状态转移**：通常通过定义一个表格或数组来记录子问题的解，随着问题规模的增加逐步填入。
3. **典型应用**：背包问题、斐波那契数列、最长公共子序列等。

**异同点：**
- **相似之处**：两者都关注将问题分解和优化求解过程，都是优化问题的方法。
- **区别**：
- **分解方式**：分治法通常是将问题拆分成两部分或更小的部分，而动态规划则是在一个维度上分解，形成一个递增的子问题系列。
- **重叠子问题**：动态规划依赖于子问题的重叠性质，利用已计算结果；分治法不一定会涉及重叠子问题，但可能有递归的重复。
- **存储策略**：动态规划常使用表格（如数组或矩阵）来存储中间结果；分治法则不需要额外存储。
- **终止条件**：动态规划通常有一个明确的结束条件，而分治法可能在每个子问题独立结束。

**相关问题--:**
1. 分治法在处理问题时如何避免重复计算？
2. 动态规划如何通过状态转移矩阵减少问题复杂度？
3. 何时会选择使用分治法而不是动态规划？