概念描述

举例

斐波那契数列问题

def f(n):
	if n==0:
		return 0
	if n==1:
		return 1
	return f(n-1)+f(n-2)

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]

跳跃游戏

问题链接

问题描述：

这道题目是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)

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

• 找到已知解，并将其作为解空间的叶子结点。 对于这个题来说，我们问的是从坐标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 

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

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

• 当前所处的位置是根节点坐标为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

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

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

总结