算法思想

贪心算法、分治算法、回溯算法、动态规划

贪心算法

针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。 每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的全局的优解。 贪心法并非从总体最优考虑，它所做出的选择仅仅是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解，但不能总获得总体最优解，通常能够获得近似最优解。贪心算法的思想简单，但是贪心法不保证能得到问题的最优解

应用：背包问题，投币问题，教室排课，任务调度。

分治算法

分而治之 ，将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治和递归：分治算法是一种处理问题的思想，递归是一种编程技巧。分治法也适合用递归实现

分治算法能解决的问题需满足:

  1. 原问题与分解成的小问题只是规模不同
  2. 子问题可以独立求解，子问题之间没有相关性
  3. 有分解终止条件，当问题足够小时，可以直接求解；
  4. 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高

MapReduce

不少创新的源泉来自对事物本质的认识。无数优秀架构设计的思想来源都是基础的数据结构和算法

//分治法
public class DividConquer {
	public static void main(String[] args) {
		int[] n = {9, 2, 4, 3, 8, 6, 7};
		f1(n, n.length - 1);
	}
	
	//求一组数的逆序对, m为n数组中最后一位下标
	//分治法适合递归处理，关键是找出递推公式
	//这种方式时间复杂度太高了O(n^2), 还可利用归并排序的细想来求
	public static void f1(int[] n, int m) {
		if (m < 1)
			return;
		for (int i = 0; i < m; i++) {
			if (n[i] > n[m]) {
				System.out.println("("+n[i]+","+n[m]+")");
			}
		}
		f1(n, m-1);
	}
}

回溯算法

人生有很多的岔路口选择，如果选错了，还可以回去重新选择。。。那该多好呀。。。 回溯思想本质就是枚举 回溯算法的复杂度比较高，是指数级别的 时间复杂度 O(2^n) 回溯算法很多时候都应用在“搜索”这类问题上。图的搜索算法，而是在一组可能的解中，搜索满足期望的解。 回溯思想本质就是枚举搜索。有规律地枚避免遗漏和重复;回溯算法也比较适合用递归实现

过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

在实现的过程中，剪枝操作是提高回溯效率的一种技巧。当满足情况就停止遍历（剪枝）

八皇后问题 背包问题 给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，如何选择，才能使得物品的总价格最高。

0-1背包 n 个物品，每个物品的重量不等，并且不可分割。期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大。 对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于 n 个物品来说，总的装法就有 2^n 种，去掉总重量超过 上限的，从剩下的装法中选择总重量最接近的，如何才能不重复地穷举出这 2^n 种装法呢？ （其实就是枚举出所有情形）

public int maxW = 0;	//记录各种装入方式的最大重量

public void getMaxW() {
	System.out.println(maxW);
}

   /**
 * 0-1背包问题，回溯法求解, 回溯的本质其实就是枚举，复杂度也是指数级的
 * @param i 第i-1个物品下标
 * @param currentW 当前背包物品重量
 * @param items 物品重量数组
 * @param itemLength 物品数量
 * @param wLimit 背包重量上限
 */
public void recall(int i, int currentW, int[] items, int itemLength, int wLimit) {
	if (currentW > wLimit|| i >= itemLength) {//超过背包上限，结束
		return;
	}
	if (currentW > maxW) {//如果大于之前最大的总重，则更新最大总重
		maxW = currentW;
	}
	//第i-1个物品没放进背包时
	recall(i+1, currentW, items, itemLength, wLimit);
	//第i-1个物品放入背包时	
	recall(i+1, currentW + items[i], items, itemLength, wLimit);
}

回溯在正则表达式中的运用 正则表达式里最重要的一种算法思想就是回溯。如何用回溯算法，判断一个给定的文本，否跟给定的正则表达式匹配？

动态规划

回溯的本质其实就是枚举，复杂度也是指数级的, 存在重复计算枚举的情况，效率太低. 动态规划比较适合用来求解最优问题，比如求最大值、最小值等，可以非常显著地降低时间复杂度。 把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。故为动态规划。

大部分动态规划能解决的问题，都可以通过回溯算法来解决，但是回溯算法解决起来效率比较低，时间复杂度是指数级的。动态规划是一种空间换时间的算法思想。

/**
 * 优惠活动满200减50 动态规划
 * @param prices 物品价格列表
 * @param num 物品数量
 * @param totalMin 满减最小价钱
 */
public void discount(int[] prices, int num, int totalMin) {
	int totalMax = 2*totalMin;
	//记录每个阶段的状态，
	boolean[][] states = new boolean[num][totalMax+1]; 
	
	states[0][0] = true;
	states[0][prices[0]] = true;
	
	for (int i = 1; i < num; i++) {
		for (int price = 0; price <= totalMax; price++ ) {
			if (states[i-1][price] == true) {
				states[i][price+0] = true;	//第i个商品不放进去时
				if (price+prices[i] <= totalMax)
					states[i][price+prices[i]] = true; //第i个商品放进去时
			}
		}
	}
	
	//找出接近200的
	int p;
	for (p = totalMin; p <= totalMax; p++) {
		if (states[num-1][p] == true) {
			System.out.println(p);
			break;
		}
	}
	if (p == totalMax) {
		System.out.println("not found");
		return;
	}
		
	//倒推出满足条件的组合
	for (int i = num - 1; i > 0; i--) {
		if (p - prices[i] > 0 && states[i-1][p - prices[i]] == true) {
			System.out.print(prices[i] + ", ");
			p = p - prices[i];
		}
	}
	if (p != 0)
		System.out.print(prices[0]);
}

一个模型三个特征 动态规划适合解决什么样的问题 多阶段决策最优解模型 一般是用动态规划来解决最优问题。问题需要经历多个决策阶段，每个决策阶段都对应着一组状态。寻找最优解的决策序列。

三个特征

  1. 最优子结构。可以通过子问题的最优解，推导出问题的最优解。
  2. 无后效性。不受之后阶段的决策影响
  3. 重复子问题

动态规划思路： 状态转移表法 ，如0-1背包问题 和直接用回溯加“备忘录”的方法，来避免重复子问题。效率差不了多少

画出一个状态表。状态表一般都是二维的，以把它想象成二维数组。每个状态包含三个变量，行、列、数组值。根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，将这个递推填表的过程，翻译成代码。 如果问题的状态比较复杂，需要很多变量来表示，比如三维、四维。那这个时候，就不适合用状态转移表法来解决了。高维状态转移表不好画图表示，另一方面是因为人脑确实很不擅长思考高维的东西。

记录每个阶段的状态根据这些状态值寻找最优解， 动态规划貌似也是遍历了所有的状态值的，但是比起回溯而言，它没有重复计算。后面一个阶段只关心前一个阶段的状态值而不关系产生这个状态值的路径，只需要留下最下的路径就可以了。

动态规划像是回溯基础，去除了重复的计算，对于像最短路径，中途经过同一个顶点的，也要做出去重，只留下最短的一条，其他的舍弃，不用继续计算。

状态转移方程法 类似递归的解题思路。根据最优子结构，写出递归公式即状态转移方程。再翻译成代码实现。有两种代码实现方法，一种是递归加“备忘录”，另一种是迭代递推。 状态转移方程是解决动态规划的关键 如 f(x,y) = min(f(x-1,y), f(x,y-1)) + matrix[x][y]

分治，贪心，回溯，动态规划小结

  1. 贪心，回溯，动态规划都可以分为多阶段决策模型；而分治法则一般不抽象为多阶段决策模型。
  2. 回溯法比较通用，基本能用贪心和动态规划解决的都能用回溯解决，因为回溯本质是穷举，时间复杂度指数级，很高，只适合数据规模小的问题。
  3. 分治法要求分割的子问题不能有重复
  4. 贪心算法通过局部最优来试图产生全局最优，每一步都选择当前最优，但是未必能得到全局最优。

这些想还需多练习和思考才能有更深的领会。

贪心：一条路走到黑，就一次机会，只能哪边看着顺眼走哪边 回溯：一条路走到黑，无数次重来的机会，还怕我走不出来 (Snapshot View) 动态规划：拥有上帝视角，手握无数平行宇宙的历史存档， 同时发展出无数个未来 (Versioned Archive View)

更新时间: