动态规划从理论到实践-深入理解贪心/分治/回溯/动态规划的算法思想

摘要：本文主要讲解常见的四种算法，分别为贪心算法：第一步选择最优的走法，算法不能做到全局最优；分治算法：一种处理问题的思想，使用递归来实现；回溯算法：我们枚举所有的解，找到满足期望的解，可以把求解过程分为多个阶段；动态规划：一个模型(多阶段决策最优解模型），三个特征(最优子结构、无后效性和重复子问题)，适用于求解最优问题。本文主要参考资料是王争的《数据结构与算法之美》，数据结构和算法作为程序员的基本功，一定得稳扎稳打的学习，我们常见的框架底层就是各类数据结构，例如跳表之于redis、B+树之于mysql、倒排索引之于ES，熟悉了底层数据结构，对框架有了更深层次的理解，在后续程序设计过程中就更能得心应手。

1、贪心算法

• 思想：对于一组数据，我们定义限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。

• 缺点：用贪心算法解决问题的思路，并不总能给出最优解。我们第一步选择最优的走法，但有可能因为第一步的选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解。

• 应用：霍夫曼编码(利用贪心算法实现对数据压缩编码)、prim和kruskal最小生成树算法、Dijkstra单源最短路径算法

实例1：霍夫曼编码(Huffman)：

假设我有一个包含1000个字符的文件，每个字符占1个byte（1byte=8bits），存储这1000个字符就一共需要8000bits，那有没有更加节省空间的存储方式呢？

解答：假设我们通过统计分析发现，这1000个字符中只包含6种不同字符，假设它们分别是a、b、c、d、e、f。而3个二进制位（bit）就可以表示8个不同的字符，所以，为了尽量减少存储空间，每个字符我们用3个二进制位来表示。那存储这1000个字符只需要3000bits就可以了。(a(000)、b(001)、c(010)、d(011)、e(100)、f(101))，利用霍夫曼编码来压缩数据，压缩率通常在20%~90%之间。我们可以把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。

注意：任何一个字符的编码都不是另一个的前缀，在解压缩的时候，我们每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。经过这种编码压缩之后，这1000个字符只需要2100bits就可以。

实现方法：我们把每个字符看作一个节点，并且辅带着把频率放到优先级队列中。我们从队列中取出频率最小的两个节点A、B，然后新建一个节点C，把频率设置为两个节点的频率之和，并把这个新节点C作为节点A、B的父节点。最后再把C节点放入到优先级队列中。重复这个过程，直到队列中没有数据。(左0右1)

实例2：分糖果

我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m<n），所以糖果只能分配给一部分孩子，每个糖果的大小不等，这m个糖果的大小分别是s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这n个孩子对糖果大小的需求分别是g1，g2，g3，……，gn。如何分配糖果，能尽可能满足最多数量的孩子？

解答：我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们期望值的贡献是一样的。我们每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。

实例3：钱币找零(使用贪心算法得到的结果不准确，最好使用动态规划)

假设我们有1元、2元、5元、10元、20元、50元、100元这些面额的纸币，它们的张数分别是c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付K元，最少要用多少张纸币呢？

解答：在生活中，我们肯定是先用面值最大的来支付，如果不够，就继续用更小一点面值的，以此类推，最后剩下的用1元来补齐。

实例4：区间覆盖(任务调度/教师排课常用)**

假设我们有n个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。我们从这n个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？

解答：我们假设这n个区间中最左端点是lmin，最右端点是rmax。这个问题就相当于，我们选择几个不相交的区间，从左到右将[lmin,rmax]覆盖上。我们按照起始端点从小到大的顺序对这n个区间排序。我们每次选择的时候，左端点跟前面的已经覆盖的区间不重合的，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间。

实例5：数字移除k个

在一个非负整数a中，我们希望从中移除k个数字，让剩下的数字值最小，如何选择移除哪k个数字呢？

解答：由最高位开始，比较低一位数字，如高位大，移除，若高位小，则向右移一位继续比较两个数字(只与右边一位比较大小)，直到高位大于低位则移除，循环k次，如：4556847594546移除5位-》455647594546-》45547594546-》4547594546-》4447594546-》444594546

实例6：等待服务

假设有n个人等待被服务，但是服务窗口只有一个，每个人需要被服务的时间长度是不同的，如何安排被服务的先后顺序，才能让这n个人总的等待时间最短？

解答：由等待时间最短的开始服务

2、分治算法 (MapReduce)(分治算法是一种处理问题的思想，递归是一种编程技巧)

从MapReduce开始讲解：它在倒排索引、pageRank计算、网页分析等搜索相关的技术中都有大量的应用。

MapReduce框架只是一个任务调度器，底层依赖GFS来存储数据，依赖Borg管理机器。它从GFS中拿数据，交给Borg中的机器执行，并且时刻监控机器执行的进度，一旦出现机器宕机、进度卡壳等，就重新从Borg中调度一台机器执行。

MapReduce应用：(并行处理能力强)

处理任务类型	示例
处理数据与数据之间存在关系的任务	统计文件中单词出现的频率
处理数据与数据之间没有关系的任务	比如对网页分析、分词等

分治算法的递归实现中，每一层递归都会涉及这样三个操作：

操作	详解
分解	将原问题分解成一系列子问题；
解决	递归地求解各个子问题，若子问题足够小，则直接求解；
合并	将子问题的结果合并成原问题

分治算法能解决的问题，一般需要满足下面这几个条件：

1. 原问题与分解成的小问题具有相同的模式；

2. 原问题分解成的子问题可以独立求解，子问题之间没有相关性(与动态规划有明显区别)

3. 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；

4. 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高。

实例1：如何快速计算出两个子问题A1与A2之间的逆序对个数呢？ (利用归并排序)

实现思路：我们可以将数组分成前后两半A1和A2，分别计算A1和A2的逆序对个数K1和K2，然后再
计算A1与A2之间的逆序对个数K3。那数组A的逆序对个数就等于K1+K2+K3

private int num = 0; // 全局变量或者成员变量
public int count(int[] a, int n) {
	num = 0;
	mergeSortCounting(a, 0, n-1);
	return num;
}
private void mergeSortCounting(int[] a, int p, int r) {
	if (p >= r) return;
	int q = (p+r)/2;
	mergeSortCounting(a, p, q);//前半部分
	mergeSortCounting(a, q+1, r);//后半部分
	merge(a, p, q, r);//合并   这三个操作相互独立
}
private void merge(int[] a, int p, int q, int r) {
	int i = p, j = q+1, k = 0;
	int[] tmp = new int[r-p+1];
	while (i<=q && j<=r) {
		if (a[i] <= a[j]) {
			tmp[k++] = a[i++];
		} else {
			num += (q-i+1); // 统计p-q之间，比a[j]大的元素个数
			tmp[k++] = a[j++];
		}
	}
	while (i <= q) { // 处理剩下的
		tmp[k++] = a[i++];
	}
	while (j <= r) { // 处理剩下的
		tmp[k++] = a[j++];
	}
	for (i = 0; i <= r-p; ++i){ // 从tmp拷贝回a
		a[p+i] = tmp[i];
	}
}

实例2：二维平面上有n个点，如何快速计算出两个距离最近的点对？

分成两块：单独求其中一块点对最小距离，然后求这两块之间点对的最小距离 通过一些排序和删除 可以减少到点对之间比较。

实例3：有两个nxn的矩阵A，B，如何快速求解两个矩阵的乘积C=A*B？

暂时还没弄灵清

实例4：分治思想在海量数据处理中的应用（很常见）

给10GB的订单文件按照金额排序这样一个需求，而我们的机器的内存可能只有2、3GB，无法一次性加载到内存，也就无法通过单纯地使用快排、归并等基础算法来解决。

我们可以将海量的数据集合根据某种方法，划分为几个小的数据集合，每个小的数据集合单独加载到内存来解决，然后再将小数据集合合并成大数据集合。我们就可以先扫描一遍订单，根据订单的金额，将10GB的文件划分为几个金额区间。比如订单金额为1到100元的放到一个小文件，101到200之间的放到另一个文件，以此类推。这样每个小文件都可以单独加载到内存排序，最后将这些有序的小文件合并，就是最终有序的10GB订单数据了

3、回溯算法

特点	详情
应用场景：	深度优先搜索、正则表达式匹配、编译原理的语法分析等
经典的数学问题：	数独、八皇后(get 8x8的棋盘格共92种解法)、0-1背包、图的着色、旅行商问题、全排列等等

回溯思想：类似枚举搜索，我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段(每个阶段你可以选择不放入物品，或是放入物品)
优点：是摸着石头过河的查找策略，且可以通过剪枝少走冤枉路，适用于缺乏规律，或是还不了解规律的搜索场景中。

实例1:0-1背包问题(物品是不可分割的，要么装要么不装)：最佳解法是动态规划，也可通过回溯法求解，贪心算法无法求解此类问题

我们有一个背包，背包总的承载重量是Wkg。现在我们有n个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

解答：我们可以把物品依次排列，整个问题就分解为了n个阶段，每个阶段对应一个物品怎么选择。加了搜索剪枝的技巧(提高搜索效率)

//感觉方法的形参太多了点
public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值
// cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了；
// w背包重量；items表示每个物品的重量；n表示物品个数
// 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
// f(0, 0, a, 10, 100)
public void f(int i, int cw, int[] items, int n, int w) {
	if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品  递归的出口
		if (cw > maxW) maxW = cw;
		return;
	}
	f(i+1, cw, items, n, w);//超出了重量(错误，不一定是超出了重量，只是一种选择而已，我不把当前物品的重量加上去)，cw不更新，考察下一个物品  精髓  借助回溯过程，实现了以每一个可能的物品，作为第一个装入背包的，以尝试所有的物品组合
	if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了，剪枝操作
		f(i+1,cw + items[i], items, n, w);  //表示选择了当前物品，cw更新为cw+items[i]
	}
}

补充：代码的第11行和第14行的顺序是可变的，即不加入当前物品重量与加入物品重量执行顺序无关

实例2：正则表达式(正则表达式中，最重要的就是通配符，通配符结合在一起，可以表达非常丰富的语义)(get)

假设正表达式中只包含“*”和“?”这两种通配符，并且对这两个通配符的语义稍微做些改变，其中，“*”匹配任意多个（大于等于0个）任意字符，“?”匹配零个或者一个任意字符，如何用回溯算法，判断一个给定的文本，能否跟给定的正则表达式匹配？

解答：依次考虑正则表达式中的每个字符，当是非通配符时，我们直接跟文本的字符进行匹配，如果相同，则继续往下处理，如果不同，则回溯。如果遇到特殊字符，有多种处理方式，也就是岔路口，可以先随机选择一种匹配方案，然后继续考察剩下的字符，如果中途发现无法继续匹配下去了，就回到这个岔路口，重新选择一种匹配方案。

public class Pattern{
	private boolean matched = false;
	private char[] pattern; // 正则表达式
	private int plen; // 正则表达式长度
	public Pattern(char[] pattern, int plen) {
		this.pattern = pattern;
		this.plen = plen;
	}
	public boolean match(char[] text, int tlen) { // 文本串及长度
		matched = false;
		rmatch(0, 0, text, tlen);
		return matched;
	}
	private void rmatch(int ti, int pj, char[] text, int tlen) {
		if(matched) return; // 如果已经匹配了，就不要继续递归了
		if(pj == plen) { // 正则表达式到结尾了
			if (ti == tlen) matched = true; // 文本串也到结尾了
				return;
		}
		if(pattern[pj] == '*') { // *匹配任意个字符
			for (int k = 0; k <= tlen-ti; ++k) {
				rmatch(ti+k, pj+1, text, tlen);
			}
		}else if (pattern[pj] == '?') { // ?匹配0个或者1个字符
			rmatch(ti, pj+1, text, tlen); //匹配0个字符
			rmatch(ti+1, pj+1, text, tlen);//匹配1个字符
		} else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配才行
			rmatch(ti+1, pj+1, text, tlen);
		}
	}
}	

4、 动态规划：(适合用来求解最优问题，比如最大值和最小值，可以显著降低时间复杂度，提高代码的执行效率)

学习的难点：求解问题的过程不太符合人类常规的思维过程

1. 通过动态规划问题模型，展示为什么需要动态规划、解题方法的演化；
2. 动态规划适合解决问题的特征，解题思路，并对比贪心、分治、回溯、动态规划思想的对比(各自特点及适用场景)；
3. 动态规划的理论与实战

实例1：0-1背包问题 对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？4种解法

第一种解法：回溯方法(穷举搜索所有可能的装法，然后找出满足条件的最大值，缺点是算法的复杂度较高，指数级别 O(2^n))
思路：递归树中的每个节点表示一种状态，我们用（i, cw）来表示。其中，i表示将要决策第几个物品是否装入背包，cw表示当前背包中物品的总重量。比如，（2，2）表示我们将要决策第2个物品是否装入背包，在决策前，背包中物品的总重量是2。

// 回溯算法实现。注意：把输入的变量都定义成了成员变量
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2，2，4，6，3}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
public void f(int i, int cw) { //调用f(0, 0)   i表示考察到哪个物品了 cw表示当前已经装进去的物品的重量和
	if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
		if (cw > maxW) maxW = cw;
		return;
	}
	f(i+1, cw); // 选择不装第i个物品，考察下一个物品  剪枝法
	if (cw + weight[i] <= w) {
		f(i+1,cw + weight[i]); // 选择装第i个物品   cw加上了weight的值
	}
}

回溯算法的缺点：有些子问题的求解是重复的，可以使用“备忘录”的解决方式，避免冗余计算

第二种解法：加了“备忘录”的回溯方法 ( 记录已经计算好的f(i, cw)，当再次计算到重复的f(i, cw)的时候，可以直接从备忘录中取出来用)（回溯+剪枝法+备忘录 牛逼）

private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2，2，4，6，3}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
private boolean[][] mem = new boolean[5][10]; // 备忘录，默认值false
public void f(int i, int cw){ // 调用f(0, 0)
	if(cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
		if(cw > maxW) maxW = cw;
			return;
	}
	if(mem[i][cw]) 
		return; //重复状态 第一次调用时绝不会执行到这儿，递归过程中会执行到，子函数无需执行，然后一层一层返回
	mem[i][cw] = true; //记录(i, cw)这个状态
	f(i+1, cw); // 选择不把第i个物品的重量计算在内，即跳过第i个物品 
	if (cw + weight[i] <= w) {  //剪枝法
		f(i+1,cw + weight[i]); // 选择装第i个物品
	}
}

知识点补充

Item	Details
return的作用域：	( 从被调用函数返回到主调函数中继续执行，并非一遇到return整个递归结束) 1、一层一层返回；2、对于有返回值的函数，递归调用必须要有return
备忘录的好处：	某次递归过程中，执行到第12行代码(if(mem[i][cw]) )后，后面的代码无需继续执行，节省时间

第三种解法：动态规划(每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合) 使用二维数组states[n][w+1],来记录每层可以达到的不同状态。

weight: 物品重量，n:物品个数，w:背包可承载重量 时间复杂度是O(nw) 空间复杂度：申请一个nw+1的二维数组 属于一种空间换时间的方法

public int knapsack(int[] weight, int n, int w) { 
	boolean[][] states = new boolean[n][w+1]; // 默认值false  状态转移表
	states[0][0] = true;          // 第一行的数据要特殊处理，可以利用哨兵优化  对应于第一个物品不放入
	states[0][weight[0]] = true;  //对应于第一个物品放入，states设置为true
	for (int i = 1; i < n; ++i) { // 动态规划状态转移
		for (int j = 0; j <= w; ++j) {// 不把第i个物品放入背包
			if (states[i-1][j] == true) 
				states[i][j] = states[i-1][j];//扫描第i个物品，不加上重量，状态设置为true
		}
		for (int j = 0; j <= w-weight[i]; ++j) {//把第i个物品放入背包
			if (states[i-1][j] == true) 
				states[i][j+weight[i]] = true;
		}//与上一个for相比，存在重复计算的问题
	}
	for (int i = w; i >= 0; --i) { // 倒序输出结果  
		if (states[n-1][i] == true) //第一个满足条件的背包即为最大的重量
			return i;
	}
	return 0;
}  

与回溯算法的对比，在数据量较大时，性能差异极大，因为动态规划避免了子问题的重复求解

第四种解答：动态规划 简化状态转移表 空间上只使用w+1的一维数组，数据的下标是已装物品的重量之和

public static int knapsack2(int[] items, int n, int w) {
	boolean[] states = new boolean[w+1]; // 默认值false
	states[0] = true; 		// 第一行的数据要特殊处理，第一个物品不放入，利用哨兵优化
	states[items[0]] = true;//第一个物品放入，states设置为true
	for (int i = 1; i < n; ++i) { //动态规划
		//j需要从大到小来处理。如果我们按照j从小到大处理的话，会出现for循环重复计算的问题
		for (int j = w-items[i]; j >= 0; --j) {//把第i个物品放入背包    
			if (states[j]==true) 
				states[j+items[i]] = true;
		}
	}
	for (int i = w; i >= 0; --i) { // 倒序输出结果
		if (states[i] == true) 
			return i;//已装物品重量和
	}
	return 0;
}

实例2：0-1背包问题升级版 两种解法

刚刚讲的背包问题，只涉及背包重量和物品重量。我们现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包在满足背包最大重量限制的前提下背包中可装入物品的总价值最大是多少呢？
第一种解法：这个问题依旧可以用回溯算法来解决

private int maxV = Integer.MIN_VALUE; // 结果放到maxV中
private int[] items = {2，2，4，6，3}; // 物品的重量
private int[] value = {3，4，8，9，6}; // 物品的价值
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
//调用f(0, 0, 0)   
//i表示即将要决策第i个物品是否装入背包，cw表示当前背包中物品的总重量，cv表示当前背包中物品的总价值
public void f(int i, int cw, int cv) { 
	if (cw == w || i == n) { //cw==w表示装满了，i==n表示物品都考察完了
		if(cv > maxV) 
			maxV = cv;
		return;
	}
	f(i+1, cw, cv); // 选择不装第i个物品     
	if (cw + weight[i] <= w) {//剪枝
		f(i+1,cw+weight[i], cv+value[i]); // 选择装第i个物品
	}
}

可以优化的空间较大，重复的i，cw的子问题。但是没法使用“备忘录”来解决这个问题 时间复杂度是O(2^n)

思路：在递归树中，每个节点表示一个状态。现在我们需要3个变量（i, cw, cv）来表示一个状态。我们发现，在递归树中，有几个节点的i和cw是完全相同的，比如f(2,2,4)和f(2,2,3)。在背包中物品总重量一样的情况下，f(2,2,4)这种状态对应的物品总价值更大，我们可以舍弃f(2,2,3)这种状态，只需要沿着f(2,2,4)这条决策路线继续往下决策就可以。也就是说，对于(i, cw)相同的不同状态，那我们只需要保留cv值最大的那个，继续递归处理，其他状态不予考虑。

第二种解法：动态规划 我们用一个二维数组states[n][w+1]，来记录每层可以达到的不同状态，二维数组的值不再是boolean类型，而对应当前状态的最大总价值。把每一层(i,cw)重复的状态合并，只记录cv值最大的哪个状态，基于此状态推断下一层的状态。good真棒

public static int knapsack3(int[] weight, int[] value, int n, int w) {
	int[][] states = new int[n][w+1];
	for (int i = 0; i < n; ++i) { // 初始化states
		for (int j = 0; j < w+1; ++j) {
			states[i][j] = -1;   //二维状态数组全部初始化为-1
		}
	}
	states[0][0] = 0;   //哨兵   对第一个位置做特殊处理   第一个物品不加入
	states[0][weight[0]] = value[0]; //第一个物品放入，states设置为value[0]
	for (int i = 1; i < n; ++i) { //动态规划，状态转移
		for (int j = 0; j <= w; ++j) { //不选择第i个物品
			if (states[i-1][j] >= 0) 
				states[i][j] = states[i-1][j];
		}
		for (int j = 0; j <= w-weight[i]; ++j){ // 选择第i个物品
			if (states[i-1][j] >= 0) {
				int v = states[i-1][j] + value[i];
				//if判断想要达到的目的是，找到这一层最大总价值的物品，然后放入数组中，避免无意义的计算
				if (v > states[i][j+weight[i]]){
					states[i][j+weight[i]] = v;
				}
			}
		}//现在两个for循环的前后顺序不能换了
	}
	// 找出最大值
	int maxvalue = -1;
	for(int j = 0; j <= w; ++j) {
		if (states[n-1][j] > maxvalue) 
			maxvalue = states[n-1][j];
	}
	return maxvalue;
}//时间复杂度是O(n*w)，空间复杂度也是O(n*w)

实例3：如何动态规划巧妙解决“双十一”购物时的凑单问题？满足200元减去50元，求买超过200元的商品最划算的买法？

思路：它跟第一个例子中讲的0-1背包问题很像，只不过是把“重量”换成了“价格”而已。购物车中有n个商品。我们针对每个商品都决策是否购买。每次决策之后，对应不同的状态集合。我们还是用一个二维数组states[n][x]，来记录每次决策之后所有可达的状态，然后利用states数组，倒推出这个被选择的商品序列。

解法：动态规划

// items商品价格，n商品个数, w表示满减条件，比如200
public static void double11advance(int[] items, int n, int w) {
	boolean[][] states = new boolean[n][3*w+1];//超过3倍就没有薅羊毛的价值了
	states[0][0] = true; // 第一行的数据要特殊处理
	states[0][items[0]] = true;
	for (int i = 1; i < n; ++i) { //动态规划
		for (int j = 0; j <= 3*w; ++j) {//不购买第i个商品
			if (states[i-1][j] == true) 
				states[i][j] = states[i-1][j];
		}
		for (int j = 0; j <= 3*w-items[i]; ++j) {//购买第i个商品
			if (states[i-1][j]==true) 
				states[i][j+items[i]] = true;
		}
	}
	int j;
	for (j = w; j < 3*w+1; ++j) { 
		if (states[n-1][j] == true) break; // 输出结果大于等于w的最小值  这两行代码妙不可言
	}
	if (j == -1) return; // 没有可行解
	for (int i = n-1; i >= 1; --i) { //i表示二维数组中的行，j表示列
		if(j-items[i] >= 0 && states[i-1][j-items[i]] == true) {
			System.out.print(items[i] + " "); // 购买这个商品
			j = j - items[i];
		} // else 没有购买这个商品，j不变
	}
	if (j != 0)
		System.out.print(items[0]);
}

实例4 杨辉三角 某一层的数字只能到达下面一层相邻的两个数字。

思路：我们站在第一层，往下移动，我们把移动到最底层所经过的所有数字之和，定义为路径的长度，求最高层到最底层的最短路径长度。
解法：使用动态规划的状态转移数组

int[][] matrix = {{5},{7,8},{2,3,4},{4,9,6,1},{2,7,9,4,5}};
public int yanghuiTriangle(int[][] matrix) {
	//值表示已累加的最短路径的长度之和
	int[][] state = new int[matrix.length][matrix.length];//状态转移数组  默认为多少？程序还不完美
	state[0][0] = matrix[0][0];//状态的值为int型 设置哨兵  值为5
	for (int i = 1; i < matrix.length; i++) {  //动态规划
		for (int j = 0; j < matrix[i].length; j++) {//分为length个阶段
			if (j == 0) 
				state[i][j] = state[i-1][j] + matrix[i][j];
			else if (j == matrix[i].length-1) 
				state[i][j] = state[i-1][j-1] + matrix[i][j];
			else {
				int top1 = state[i-1][j-1];
				int top2 = state[i-1][j];
				state[i][j] = Math.min(top1, top2) + matrix[i][j];
			}
		}
	}
	int minDis = Integer.MAX_VALUE;
	for (int i = 0; i < matrix[matrix.length-1].length; i++) {
		int distance = state[matrix.length - 1][i];//最后一行
		if (distance < minDis) minDis = distance;
	}
	return minDis;
} 

动态规划理论

1、什么样的问题可以用动态规划解决？(动态规划能解决的问题有什么规律可循呢？)
一个模型(多阶段决策最优解模型,每个决策阶段都对应着一组状态)三个特征(最优子结构、无后效性和重复子问题)

特点	详情
最优子结构：	后面阶段的状态可以通过前面阶段的状态推导出来。
无后效性：	某阶段状态一旦确定，就不受之后阶段的决策影响
重复子问题	没啥好说的

实例5：nxn棋盘格，从左上角开始，到右下角终止，每次只能向右或向下移动一位，求最短路径？

符合一个模型：共有2*(n-1)个状态，定义为min_dist(i,j),值表示(0,0)到(i,j)的最短路径长度。也符合重复子问题，无后效性，最优子结构。递推公式：min_dist(i,j)=w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

2、解决动态规划问题的一般思考过程是什么样的？
状态转移表法和状态转移方程法

1. 状态转移表法(前边的背包、双十一问题求解都是用的这种方法)

   状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。

解法1：回溯法

private int minDist = Integer.MAX_VALUE; // 全局变量或者成员变量
// 调用方式：minDistBacktracing(0, 0, 0, w, n);
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
	// 到达了n-1, n-1这个位置了，这里看着有点奇怪哈，你自己举个例子看下
	if (i == n && j == n) {
		if (dist < minDist) minDist = dist;
		return;
	}
	if (i < n) { // 往下走，更新i=i+1, j=j
		minDistBT(i + 1, j, dist+w[i][j], w, n);
	}
	if (j < n) { // 往右走，更新i=i, j=j+1
		minDistBT(i, j+1, dist+w[i][j], w, n);
	}	
}

解法二：动态规划 状态转移表

public int minDistDP(int[][] matrix, int n) {
	int[][] states = new int[n][n];//状态转移表   值为当前最短路径
	int sum = 0;
	for (int j = 0; j < n; ++j) { // 初始化states的第一行数据
		sum += matrix[0][j];
		states[0][j] = sum;
	}
	sum = 0;
	for (int i = 0; i < n; ++i) { // 初始化states的第一列数据
		sum += matrix[i][0];
		states[i][0] = sum;
	}
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j < n; ++j) {
			states[i][j] =matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);
		}
	}
	return states[n-1][n-1];
}

2、状态转移方程 两种实现方式：递归+备忘录 迭代递推
解法三：递归+备忘录

private int[][] matrix ={{1，3，5，9}, {2，1，3，4}，{5，2，6，7}，{6，8，4，3}};
private int n = 4;
private int[][] mem = new int[4][4];  //备忘录 初始化全为0
public int minDist(int i, int j) { // 调用minDist(n-1, n-1);
	if (i == 0 && j == 0) return matrix[0][0];//结束条件
	if (mem[i][j] > 0) return mem[i][j];
	int minLeft = Integer.MAX_VALUE;
	if (j-1 >= 0) {
		minLeft = minDist(i, j-1);
	}
	int minUp = Integer.MAX_VALUE;
	if (i-1 >= 0) {
		minUp = minDist(i-1, j);
	}
	int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);//状态转移方程
	mem[i][j] = currMinDist;
	return currMinDist;
}

3、贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系？

方法	特点	缺点
贪心、回溯、动态规划	多阶段决策最优解模型	/
回溯算法	相当于穷举算法，穷举所有的情况，然后对比得到最优解，基本上能用动态规划、贪心解决的问题，都可以用回溯算法解决	缺点是算法的时间复杂度非常高，指数级别，只能解决小规模数据的问题。
动态规划	高效的原因：问题中存在大量的重复子问题	/
贪心算法	是动态规划的一种特殊情况，由局部最优解构成全局最优解	但是可以解决的问题很有限。

实例6：硬币找零问题

我们在贪心算法那一节中讲过一次。我们今天来看一个新的硬币找零问题。假设我们有几种不同币值的硬币v1，v2，……，vn（单位是元）。如果我们要支付w元，求最少需要多少个硬币？比如，我们有3种不同的硬币，1元、3元、5元，我们要支付9元，最少需要3个硬币（3个3元的硬币或者是1、3、5也是3枚硬币 题目没出好）
可以看做爬阶梯问题，分别可以走1、3、5步，怎么最少走到9步，动态转移方程为f(9)=1+min(f(8),f(6),f(4))
第一种解法：动态规划-状态转移表

public int minCoins(int money) {
	if (money == 1 || money == 3 || money == 5) return 1;
	boolean [][] state = new boolean[money][money + 1];//一维是支付硬币个数  二维是当前已支付钱数
	if (money >= 1) state[0][1] = true;
	if (money >= 3) state[0][3] = true;
	if (money >= 5) state[0][5] = true;//第一次支付时，存在三种状态
	for (int i = 1; i < money; i++) {
		for (int j = 1; j <= money; j++) {
			if (state[i - 1][j]) {
				if (j + 1 <= money) state[i][j + 1] = true;
				if (j + 3 <= money) state[i][j + 3] = true;
				if (j + 5 <= money) state[i][j + 5] = true;
				if (state[i][money]) return i + 1;
			}
		}
	}
	return money;     //顺序分别为5、3、1
}

第二种解法： 动态规划-状态转移表 来自课后的一个答案，更加符合状态转移表的求解过程

public static int countMoneyMin(int[] moneyItems, int resultMemory) {
    if (null == moneyItems || moneyItems.length < 1) {
         return -1;
     }
     if (resultMemory < 1) {
         return -1;
     }
     // 计算遍历的层数，此按最小金额来支付即为最大层数
     int levelNum = resultMemory / moneyItems[0];
     int leng = moneyItems.length;
     int[][] states = new int[levelNum][resultMemory + 1];//状态转移表   值为已支付价格
     // 初始化状态数组
     for (int i = 0; i < levelNum; i++) {
         for (int j = 0; j < resultMemory + 1; j++) {
             states[i][j] = -1;
         }
     }
     // 将第一层的数据填充
     for (int i = 0; i < leng; i++) {
         states[0][moneyItems[i]] = moneyItems[i];
     }
     int minNum = -1;
     // 计算推导状态
     for (int i = 1; i < levelNum; i++) {
         // 推导出当前状态
         for (int j = 0; j < resultMemory; j++) {
             if (states[i - 1][j] != -1) {
                 // 遍历元素,进行累加
                 for (int k = 0; k < leng; k++) {
                     if (j + moneyItems[k] <= resultMemory) {
                         states[i][j + moneyItems[k]] = moneyItems[k];
                     }
                 }
             }
             // 找到最小的张数
             if (states[i][resultMemory] >= 0) {
                 minNum = i + 1;
                 break;
             }
         }
         if (minNum > 0) {
             break;
         }
     }
     int befValue = resultMemory;
     // 进行反推出，币的组合
     for (int i = minNum - 1; i >= 0; i--) {
         for (int j = resultMemory; j >= 0; j--) {
             if (j == befValue) {
                 System.out.println("当前的为:" + states[i][j]);
                 befValue = befValue - states[i][j];
                 break;
             }
         }
     }
     return minNum;
}	

动态规划实战：

实例7：量化两个字符串的相似度(编辑距离：将一个字符串转换成另一个字符串，需要的最少编译操作次数(增加/删除/替换))

计算方法：莱文斯坦距离(允许增加/删除/替换操作)和最长公共子串长度(增加/删除)。如何编程计算莱文斯坦距离？
第一种解法：回溯法 如果a[i]与b[j]匹配，我们递归考察a[i+1]和b[j+1]。如果a[i]与b[j]不匹配，那我们有多种处理方式可选(可以删除a[i]，然后递归考察a[i+1]和b[j]；可以删除b[j]，然后递归考察a[i]和b[j+1]；可以在a[i]前面添加一个跟b[j]相同的字符，然后递归考察a[i]和b[j+1];可以在b[j]前面添加一个跟a[i]相同的字符，然后递归考察a[i+1]和b[j]；可以将a[i]替换成b[j]，或者将b[j]替换成a[i]，然后递归考察a[i+1]和b[j+1])

//我们将上面的回溯算法的处理思路，翻译成代码

	private char[] a = "mitcmu".toCharArray();
	private char[] b = "mtacnu".toCharArray();
	private int n = 6;
	private int m = 6;
	private int minDist = Integer.MAX_VALUE; // 存储结果
	// 调用方式 lwstBT(0, 0, 0);
	public void lwstBT(int i, int j, int edist) { //edist为最小操作次数
		if (i == n || j == m) { //终止条件
			if (i < n) edist += (n-i);
			if (j < m) edist += (m - j);
			if (edist < minDist) minDist = edist;
				return;
		}
		if (a[i] == b[j]) { //两个字符匹配
			lwstBT(i+1, j+1, edist);  //分别考察下一个字符
		} else { // 两个字符不匹配
			lwstBT(i + 1, j, edist + 1); //删除a[i]或者b[j]前添加一个字符
			lwstBT(i, j + 1, edist + 1); //删除b[j]或者a[i]前添加一个字符
			lwstBT(i + 1, j + 1, edist + 1); //将a[i]和b[j]替换为相同字符
		}
	}

对于这个问题，状态(i, j)可能从(i-1, j)，(i, j-1)，(i-1, j-1)三个状态中的任意一个转移过来

第二种解法：动态规划 状态转移表/转移方程
现在既有状态转移方程，又理清了完整的填表过程，代码实现就简单了

public int lwstDP(char[] a, int n, char[] b, int m) {
	int[][] minDist = new int[n][m]; //值为最小操作次数
	for (int j = 0; j < m; ++j){ //初始化第0行:a[0..0]与b[0..j]的编辑距离
		if(a[0] == b[j]) 
			minDist[0][j] = j;
		else if(j != 0) 
			minDist[0][j] = minDist[0][j-1]+1;
		else 
			minDist[0][j] = 1;
	}
	for (int i = 0; i < n; ++i) {//初始化第0列:a[0..i]与b[0..0]的编辑距离
		if (a[i] == b[0]) 
			minDist[i][0] = i;
		else if(i != 0) 
			minDist[i][0] = minDist[i-1][0]+1;
		else 
			minDist[i][0] = 1;
	}//以上为初始化操作
	for (int i = 1; i < n; ++i) { //按行填表
		for (int j = 1; j < m; ++j) {
			if (a[i] == b[j]) minDist[i][j] = min(minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]);
			else minDist[i][j] = min(minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]+1);
		}
	}
	return minDist[n-1][m-1];
}
private int min(int x, int y, int z) {
	int minv = Integer.MAX_VALUE;
	if (x < minv) minv = x;
	if (y < minv) minv = y;
	if (z < minv) minv = z;
	return minv;
}

实例8：如何编程计算最长公共子串长度？

直接定义状态，然后写状态转移方程 每个状态还是包括三个变量(i, j, max_lcs)，max_lcs表示a[0…i]和b[0…j]的最长公共子串长度
解法：动态规划 状态转移方程
思路：我们从a[0]和b[0]开始，依次考察两个字符串中的字符是否匹配。如果a[i]与b[j]互相匹配，我们将最大公共子串长度加一，并且继续考察a[i+1]和b[j+1]。如果a[i]与b[j]不匹配，最长公共子串长度不变，这个时候，有两个不同的决策路线：删除a[i]，或者在b[j]前面加上一个字符a[i]，然后继续考察a[i+1]和b[j]；删除b[j]，或者在a[i]前面加上一个字符b[j]，然后继续考察a[i]和b[j+1]
状态转移方程：如果：a[i]==b[j]，那么：max_lcs(i, j) 就等于：max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1))；如果：a[i]!=b[j]，那么：max_lcs(i, j)就等于：max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1))；

public int lcs(char[] a, int n, char[] b, int m) {	
	int[][] maxlcs = new int[n][m];//值为最长公共子串
	for (int j = 0; j < m; ++j) {//初始化第0行：a[0..0]与b[0..j]的maxlcs
		if (a[0] == b[j]) maxlcs[0][j] = 1;
		else if (j != 0) maxlcs[0][j] = maxlcs[0][j-1];
		else maxlcs[0][j] = 0;
	}
	for (int i = 0; i < n; ++i) {//初始化第0列：a[0..i]与b[0..0]的maxlcs
		if (a[i] == b[0]) maxlcs[i][0] = 1;
		else if (i != 0) maxlcs[i][0] = maxlcs[i-1][0];
		else maxlcs[i][0] = 0;
	}
	for (int i = 1; i < n; ++i) { // 填表
		for (int j = 1; j < m; ++j) {
			if (a[i] == b[j]) maxlcs[i][j] = max(maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]+1);
			else maxlcs[i][j] = max(maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]);
		}
	}
	return maxlcs[n-1][m-1];
}
private int max(int x, int y, int z) {
	 int maxv = Integer.MIN_VALUE;
	 if (x > maxv) maxv = x;
	 if (y > maxv) maxv = y;
	 if (z > maxv) maxv = z;
	 return maxv;
}

搜索引擎纠错效果优化思路？

1. 不仅取出编辑距离最小的那个单词，而且取出编辑距离最小的TOP10，然后根据其他参数，决策选择哪个单词作为拼写纠错单词。比如使用搜索热门程度来决定哪个单词作为拼写纠错单词。

2. 还可以用多种编辑距离计算方法，比如今天讲到的两种，然后分别编辑距离最小的TOP 10，然后求交集，用交集的结果，再继续优化处理。

3. 还可以通过统计用户的搜索日志，得到最常被拼错的单词列表，以及对应的拼写正确的单词。搜索引擎在拼写纠错的时候，首先在这个最长被拼错单词列表中查找。如果一旦找到，直接返回对应的正确的单词。这样纠错的效果非常好。

4. 我们还有更加高级一点的做法，引入个性化因素。针对每个用户，维护这个用户特有的搜索喜好，也就是常用的搜索关键词。当用户输入错误的单词的时候，我们首先在这个用户常用的搜索关键词中，计算编辑距查找编辑距离最小的单词。

针对纠错性能方面，两种基于分治的优化方式

1、如果纠错功能的TPS不高，我们可以部署多台机器，每台机器运行一个独立的纠错功能。当有一个纠错请求的时候，我们通过负载均衡，分配到其中一台机器，来计算编辑距离，得到纠错单词
2、如果纠错系统的响应时间太长，也就是，每个纠错请求处理时间过长，我们可以将纠错的词库，分割到很多台机器。当有一个纠错请求的时候，我们就将这个拼写错误的单词，同时发送到这多台机器，让多台机器并行处理，分别得到编辑距离最小的单词，然后再比对合并，最终决定出一个最优的纠错单词。

实例9(常考)：我们有一个数字序列包含n个不同的数字，如何求出这个序列中的最长递增子序列长度？

比如2, 9, 3, 6, 5, 1, 7这样一组数字序列，它的最长递增子序列就是2, 3, 5, 7，所以最长递增子序列的长度是4
递推公式:a[0…i] 的最长子序列为: a[i] 之前所有比它小的元素中子序列长度最大的 + 1
// 动态规划求 a 的最上升长子序列长度

public class 动态规划求解最长子序列长度 {
// 动态规划求 a 的最上升长子序列长度
static int longestSubsequence(int[] a, int n) {
	// 创建一个数组, 索引i对应考察元素的下标, 存储 arr[0...i] 的最长上升子序列大小
	int[] lss_lengths = new int[n];
	// 第一个元素哨兵处理
	lss_lengths[0] = 1;
	// 动态规划求解最长子序列
	int i, j, max;
	for (i = 1; i <n; i++) {
	    // 计算 arr[0...i] 的最长上升子序列
	     // 递推公式: lss_lengths[i] = max(condition: j < i && a[j] < a[i] value: lss_lengths[j] + 1)
	     max = 1;
	     for (j = 0; j < i; j++) {
	             if (a[i] > a[j] && lss_lengths[j] >= max) {
	                     max = lss_lengths[j] + 1;
	             }
	     }lss_lengths[i] = max;
	}
	int lss_length = lss_lengths[n-1];
	return lss_length;
}
public static void main(String[] args) { 
	int[] arr = { 2, 9, 3, 6, 5, 1, 7 };
	int longestSubsequence = longestSubsequence(arr, arr.length);
	System.out.println(longestSubsequence);   
}

结语：脚踏实地，一分耕耘一分收获 fighting