分治算法

分治问题，个人感觉叫分解问题更容易记忆
核心，即把难以解决的大问题分成若干个小问题。在这里，将大问题分解为小问题是本方法的核心难点。

1. 分解的小问题必须是可解的，这里的‘可解’在我看来是逻辑上易于解决，同时方便将各个小问题的解叠加为大问题的解。
2. 从1中有些人可能不明白我说的意思，将一个大问题分解，分解的方法可能有很多，但是我们为了便于解决，就要遵循1中的建议来进行分解。

---

分治问题的经典案例

汉诺塔问题

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？这里我们假设将a上的圆盘移动到c上

首先面对这样一个问题，我们一开始肯定想的是先移动几个，看看有没有规律可循。但是这种方法很让人头痛，移动了几步之后，感觉并没有什么规律可循。

• 分解问题
  一股脑地考虑每一步如何移动很困难，我们可以换个思路。先假设除最下面的盘子之外，我们已经成功地将上面的63个盘子移到了b柱，此时只要将最下面的盘子由a移动到c即可。规模由64变为了63。因此可以采用相同的方法，先将上面的62个盘子由b移到a，再将最下面的盘子移到c……对照下面的过程，试着是否能找到规律：
  

1. 将b柱子作为辅助，把a上的63个圆盘移动到b上
2. 将a上的最后一个圆盘移动到c
3. 将a作为辅助，将b上的62个圆盘移动到a上
4. 将b上的最后一个圆盘放在c上

public static void resolve(int n, Stack<Integer> a, Stack<Integer> b, Stack<Integer> c) {
            if (n==0) return;
            //将a上的n-1个盘子移动到B(以C为中转)
            resolve(n-1, a, c, b);
            //将最后一个盘子移动到C
            c.push(a.pop());
            //将b上的盘子移动到C (以a为中转),完成任务！
            resolve(n-1, b, a, c);
      }

时间复杂度的求解

假设移动n个圆盘需要f(n)次移动
当有一个圆盘时，只需一步f(1) = 1
当有n个圆盘时，假设开始圆盘在A柱，将A柱的n-1个圆盘移动到B，再将A剩下的一个移动到C，最后将B的n-1个移动到C。
即：f(n) = 2f(n-1)+1
可求出 f(n) = 2^(n-1) 即o(n) = 2^n