分治介绍

分治 #

分而治之算法可以分成三个部分：

1. 分解原问题为多个子问题（原问题的多个小实例）。
2. 解决子问题，用返回解决子问题的方式的递归算法。递归算法的基本情形可以用来解决子问题。
3. 组合这些子问题的解决方式，得到原问题的解。

应用：

• 归并排序
• 快速排序

• 二分搜索
• 374.猜数字大小

• 226.反转二叉树
• 100.相同的树
• 101.对称二叉树

DP（动态规划） #

分治 是把问题分解成相互独立的子问题

DP 是将问题分解成相互依赖的子问题