动态规划、回溯法、贪心算法的区别与联系_动态规划和回溯法的区别

概念描述

• 回溯法。回溯法被称为是万能的解法，几乎所有问题都可以用回溯法去解题。其核心思想就是枚举每一种情况，然后进行比较，最终得到最优解。这个算法的时间复杂度一般在指数级别O(2^n)。
• 动态规划。常用来求解可划分的问题。对于一个问题，它可以划分为由若干个子问题相互联系产生，那么就可以用动态规划来求解。
• 贪心。每次求得局部最优解，将局部最优解累加起来就变成了全局最优解。
• 问题。能够用动态规划和回溯法解答的题目都很有特点。一般来说就是多阶段，当前要求解的问题和其子问题有关，并且子问题的抉择影响到了后面的答案。如果当前问题规模记为f(n)的话，那么f(n)一定和f(n-1)或者f(n-2)有关系，可以是f(n)=f(n-1)+f(n-2)，也可以是f(n)=max/min(f(n-1)+1,f(n-2))等等。具体要看问题描述。

以上三个算法的基本概念，网上有更多资料，这里就不详细展开了。接下来讲我在学习过程中遭遇的问题。在实际运用这些算法解题的时候，经常会看到一些很奇怪的名词，比如解空间、自顶向下解法、自底向上解法等等。那么这些词到底代表的是什么含义呢？接下来通过一些具体的例子和图来展示。

举例

斐波那契数列问题

问题描述
斐波那契数列是通过"递归"定义的，通过这个递归关系式，我们可以知道斐波那契数列中任意一个位置的数值。给你一个数字n，你能求出它对应的数列值是多少嘛？

回溯法
如果要求F(n)，那么必须要知道F（n-1）和F（n-2）。其问题就变成了求F(n-1)和F（n-2）。
举个例子，当我们计算f（7）的时候，必须要知道f(5)和f(6)，而计算f(5)又必须要知道f(3)和f(4)，直到问题规模缩小至f(0)和f(1)的时候，我们才能够根据已有的条件得到答案，然后往上回推。

• 那么这个过程，就叫做自顶向下的分析过程。
• 分析过程形成的树状图就叫做解空间。 当我们从根节点扩展到叶子节点(叶子节点是有解的最小问题)的时候,就意味着我们从解空间找到了一个解。所以，只要构造好了解空间树，求解的过程就是从根节点遍历到叶子节点的过程。
• 整个分析阶段是不断把问题化解为子问题，直到子问题的规模有解的时候，再开始回推进行计算。
• 使用回溯法存在的最主要问题就是存在大量重复计算，当计算f(7)的时候，需要计算f(5)和f(6)。而当计算f(6)的时候，需要再次计算下f(5)。

代码示意如下

def f(n):
	if n==0:
		return 0
	if n==1:
		return 1
	return f(n-1)+f(n-2)
1
2
3
4
5
6

动态规划
使用回溯法解题的时候，习惯于把大问题分解，分解到问题规模可解的时候，再去解决问题。而动态规划则是从已知解出发，逐步推算到问题规模的程度。

• 回溯法。大问题————>分解为子问题————>子问题的规则足够小(可解)————>回推大问题。
• 动态规划。已知有解的子问题————>逐步推算到问题规模大小的大问题。

对于斐波那契数列问题而言，还拿f(7)举例，其过程如下：

• 已知解f(1)和f(2)。推算得到f(3)。
• f(3)+f(2)————》f(4)
• f(4)+f(3)————》f(5)
• f(5)+f(4)————》f(6)
• f(6)+f(5)————》f(7)

通过分析这个过程可以知道，动态规划的出发点是叶子节点，通过公式，逐步的从叶子结点上推到根节点。其核心思想就是通过已知解，来求解未知解。直到求解到的问题规模符合题目要求的规模
代码实现如下：

def f(n):
	#定义一个长度为n+1的数组，用来存储和记录已经计算过的值
	a=[0]*(n+1)
	# 初始化已知解
	a[0]=0,a[1]=1
	# 利用公式进行递推，不断推导未知解，直到求出自己想要的未知解，停止。
	for i in range(2,n+1):
		a[i]=a[i-1]+a[i-2]
	return a[n]
1
2
3
4
5
6
7
8
9

总结
上文主要描述了解题的时候，回溯法和动态规划之间的区别。主要有以下几点。

• 回溯法。要实现回溯法解题，那么就要将问题规模进行切分，直到将问题切分到可解的时候再进行计算。
  • 时间复杂度O(2^n)。一般为指数级别，存在大量的重复计算，已经计算过的结果无法得到有效重用。
• 动态规划。从已知解推导问题，将问题推导到要求的未知解的规模即可。
  • 时间复杂度一般为遍历数组的复杂度。没有重复计算，会使用数组记录到之前已经计算出来的值。
• 如果遇到某些问题，问题分多个阶段，且当前阶段的结果会影响到后续的结果，那么这个问题就可以用回溯或者动态规划来求解。

跳跃游戏

问题链接

问题描述：

这道题目是leetcode的原题，其官方解答对理解动态规划和回溯的优异和异同具有很大的帮助。官方解答过程：回溯法——》带记忆表的回溯法———》动态规划——》贪心。

回溯法

首先，通过题目可以知道这是一个多阶段问题。拿例子[2,3,1,1,4]为例。位置0的值为2，因此可以跳到位置1和位置2。到底跳到位置几，需要我们自己判断。如果判断不出来，那么最简单的思路就是枚举。把所有情况都枚举一遍。我用了一幅图来表示枚举的过程。

• 首先，定义节点。对图中的元素进行解释。每个节点都是(索引,数组值)的这种形式。比如[2,3,1,1,4]就是图下的这几个节点。2的节点是(0,2)，以此类推。
• 确定叶子节点和根节点。对于[2,3,1,1,4]这个例子而言。问你能否到达最后一个位置？也就是位置4。那么我们目前不知道位置0,1,2,3是否能到达位置4。但我们确定位置4一定能到达最后一个位置，因为位置4就是最后一个位置，所以我们得到了已知解位置4，也就是叶子结点（4,4）。而我们的出发点是位置0，所以我们确定了根节点（0,2）。
• 绘制解空间。
  • 从位置0出发，因为其元素是2，所以可以知道，下一跳能够到达的坐标是1和2。
  • 从位置1出发，因为其元素是3，所以，下一跳能够到达的坐标是2,3,4。
  • 从位置2出发，因为其元素是1，所以，下一跳能够到达的坐标是3。
  • 从位置3出发，因为其元素是1，所以，下一跳能够到达的坐标是4。
  • 每次绘制，只需要关注当前节点能够扩展出来的节点有哪些，然后绘制就行。即每次绘制，只需要推断出当前节点的子节点。
• 绘制完解空间后，我们就可以得到结论，可以到达最后位置，并且有4条路可以选择。甚至我们可以通过图示得到从哪走跳是最快的。
  

# 我用伪代码描述下这个过程。
# 给定一个数组a和它开始跳的时候的下标。
def can_jump_from_position(pos,a):
	#如果到达叶子节点（已知解），那么一定可以到达。
	if pos == len(a):
		return True
		
	#对当前节点进行扩展，推导它的子节点。
	furthest_jump = min(a[pos]+pos,len(a)-1) #当前节点最远能跳的距离受制于数组下标的最大值。不能超过数组下标。
	#扩展子节点
	for next_pos in range(pos+1,furthest_jump+1):
		# 子节点有解，则父节点也一定有解，故返回True
		if can_jump_from_postion(next_pos,a):
			return True
	#所有子节点都无解，返回False
	return False

#调用该回溯算法	
def can_jump(a):
	return can_jump_from_postion(0,a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

回溯法总结
对于一个问题，如果用回溯法解题，可以抽象出这样的思路。

• 找到已知解，并将其作为解空间的叶子结点。 对于这个题来说，我们问的是从坐标0能否到达最后一个坐标。那么对于我们来说，我们并不知道坐标0,1,2等等是否能到达最后一个坐标。但可以肯定最后一个坐标肯定是满足题目解的。即最后一个坐标一定能抵达最后一个坐标，而第一个是否能够抵达，我们并不知道。因此，就把最后一个坐标当做已知解。
• 找到根节点。 这个需要找问题的出发点，也就是最初的原始问题。对于这个题来说，原始问题就是从坐标0是否可达最后一个坐标。那么根节点就是坐标0。
• 从根节点开始扩展子节点，直至到达叶子节点。 开始构造解空间，对于每个当前节点，都去遍历其可能的子节点，已知扩展，知道到达叶子节点（递归出口）。
• 整个从根节点到叶子节点的过程，就是自顶向下的分析过程

回溯优化

对于整个回溯过程，普遍存在的问题是会存在着大量计算。比较好的优化思路是使用一个数组去记录已经得到的解。这样下次查询的时候，先判断一下是否已经解过了就好了。这个思路，leetcode有相应的说明。可以看题解。其中初始化最后一个坐标为GOOD的原因是它就是我们已经知道的已知解。

动态规划

对于动态规划来说，其核心思想就是通过已知解求解未知解。对当前这个题目来说，已知解就是最后一个坐标是能够到达最后一个坐标的。最后一个坐标就是叶子节点，问题是能否从坐标0到达最后一个节点，坐标0就是根节点。整个从叶子结点（已知解）到根节点（未知问题）的分析过程，就是自下而上的分析过程。

拿[2,3,1,1,4]这个例子来说，已知位置4是能够到达最后一个坐标的，是已知解，是叶子结点。接下来只需要判断其叶子节点的上一层能否有解即可缩小问题规模。比如说位置3是可以到达位置4的，那么整个问题就从“是否能从位置0到最后一个位置(位置4)”变为“是否能从位置0到达位置3”。因为位置3是可以到达位置4的。

其过程如下：

• 已知最后一个节点坐标为4，其是有解的。
• 逆序遍历数组，当前节点为倒数第二个坐标（坐标3），发现坐标3的元素是1，可以到达坐标4，标记坐标3可达。
• 逆序遍历数组，当前节点为坐标2，发现坐标2的元素是1，可以到达坐标3，标记坐标2可达。
• 逆序遍历数组，当前节点为坐标1，发现坐标1的元素是3，可以到达坐标2,3,4，标记坐标1可达。
• 逆序遍历数组，当前节点为坐标0，发现坐标0的元素是2，可以到达坐标1,2，标记坐标0可达。
• 最终得到答案
  

代码思路展示

#需要从已知解出发，扩展出未知解。

def can_jump(a):
	#使用一个数组记录解的情况
	a_len = len(a)
	dp = [0]*a_len
	
	#初始化已知解,最后一个坐标一定可达
	dp[a_len-1] = 1 
	
	#从叶子节点往上倒推，并把有解的记录下来。
	for i in range(a_len-2,-1,-1):
		furthest_jump = min(a[i]+i,a_len-1)
		#遍历当前节点的所有子节点
		for j in range(i,furthest_jump+1):
			#如果子节点有解，那么当前节点一定有解
			if dp[j] == 1:
				dp[i] == 1
	return dp[0] == 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

贪心算法
对于这个问题，还有一种解法，就是贪心算法。如果一个问题能使用贪心解决，那么需要它的每个子问题的最优解都是全局最优解的一部分。其实，我感觉判断是否可以用贪心，多半靠经验，如果刷题的话，不太好证明到底能不能用贪心，只能举反例。

还是这个解空间，其贪心过程如下。

• 当前所处的位置是根节点坐标为0，其下一层能够到达的节点有1和2。此时如果是回溯法，则会进行枚举，坐标1和坐标2都试试，而贪心则会根据某种策略选择某一个坐标。
• 这里比较难的就是贪心条件的设定，如果设置为局部最优（当前能跳的最远点），这里就是指节点2。那么明显能看出这不是最优解。应该设定为下一层中能跳的最远的点。节点1最远能跳到4，而节点2最远能跳到节点3。因此此次贪心选择节点1。
• 节点1可达的下层节点有2,3,4。这个时候会选择能够到达最远的那个点，2最远到达3,3最远到达4,4最远能够到达8。因此会选择8。
  
  代码示意如下

def can_jump(a):
	# end 记录下层能跳的边界
	# max_pos记录下层能跳的最大距离
	# step 记录跳数
	end = max_pos = 0 
	for i in range(0,len(a)):
		# 出现0的时候max_pos有可能会停滞，如果停滞了，那就代表无法继续了
		if i < max_pos:
			return False 
		max_pos = max(a[i]+i,max_pos)
		#当前层已走完，记录下一层的边界
		if end == i :
			step += 1
			end = max_pos
	return max_pos > len(a)-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这种方法也可以记录跳数。

以上代码都是白板乱写的，不一定能运行，大家看个思路就好。

总结

本篇文章主要讲了DP和回溯法解题的区别。我觉得最主要的有以下几点。

1. 理解解空间的构成，解空间中叶子节点是已知解，根节点是待解的问题。
2. 回溯主要是自顶向下的求解过程，求解过程是从根节点到叶子结点。不断从根节点扩展出新的节点
3. 动态规划主要是自底向上的求解过程，是从叶子结点（已知解）推导出根节点（未知解）的过程。
4. 贪心则是一个局部最优的搜索过程。.

其实我觉得能看懂自顶向下和自底向上的分析过程就是最大的收获了