【Java -- 算法】回溯法

前言

一句话理解四种算法思想

• 分治：分而治之，先解决子问题，再将子问题的解合并求出原问题。
• 贪心：一条路走到黑，选择当下局部最优的路线，没有后悔药。
• 回溯：一条路走到黑，手握后悔药，可以无数次重来。(英雄联盟艾克大招无冷却)。
• 动态规划：上帝视角，手握无数平行宇宙的历史存档，同时发展出无数个未来。

分治算法

分治算法思想很大程度上是基于递归的，也比较适合用递归来实现。顾名思义，分而治之。一般分为以下三个过程：

• 分解：将原问题分解成一系列子问题。
• 解决：递归求解各个子问题，若子问题足够小，则直接求解。
• 合并：将子问题的结果合并成原问题。

比较经典的应用就是归并排序 (Merge Sort) 以及快速排序 (Quick Sort) 等。

public static void compose(int[] arr, int start, int end) {
	int[] atmp = new int[end - start];
	//获取中间的位置
    int center = (start + end) / 2;
	//要改变指针的话对指针作一个备份
    int a = start, b = center, c = end;

	//定义一些记录值（标记值）
    int i = 0;
	//做相应的处理，如归并中是将左边与右边的数据排序并组合到一起
    while (a