动态规划和递归分治的区别

动态规划和递归分治都是算法设计中的两种常用技术，它们在解决问题时有着不同的思路和应用场景。

**动态规划（Dynamic Programming, DP）**：
- 动态规划通常用于解决具有重叠子问题和最优子结构的问题，如最短路径、背包问题等。
- 它的工作原理是将大问题分解成更小的子问题，并保存子问题的解，避免重复计算，从而提高效率。
- 动态规划通常采用自底向上的策略，从最小的子问题开始，逐步构建出最终的解决方案。
- 相关问题：动态规划如何避免重复计算？有哪些经典问题可以用动态规划解决？

**递归分治（Divide and Conquer）**：
- 递归分治是一种将问题分解成较小的相同或相似的子问题，然后分别解决这些子问题，最后合并子问题的解得到原问题的解的方法。
- 递归过程通常包括三个步骤：分解（divide）、解决（conquer）和合并（combine）。
- 它并不一定涉及保存中间结果，子问题的解决可能独立于主问题的求解过程。
- 例如，排序（如快速排序、归并排序）和查找（如二分查找）通常使用递归分治策略。
- 相关问题：递归分治的核心思想是什么？递归何时会终止？

总结一下，动态规划侧重于优化子问题的解并避免重复，而递归分治更关注问题的分解和合并。