问题描述
斐波那契数列是通过"递归"定义的，通过这个递归关系式，我们可以知道斐波那契数列中任意一个位置的数值。给你一个数字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)
动态规划
 使用回溯法解题的时候，习惯于把大问题分解，分解到问题规模可解的时候，再去解决问题。而动态规划则是从已知解出发，逐步推算到问题规模的程度。
 
回溯法。大问题————>分解为子问题————>子问题的规则足够小(可解)————>回推大问题。
动态规划。已知有解的子问题————>逐步推算到问题规模大小的大问题。
 
对于斐波那契数列问题而言，还拿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]
总结
 上文主要描述了解题的时候，回溯法和动态规划之间的区别。主要有以下几点。
 
回溯法。要实现回溯法解题，那么就要将问题规模进行切分，直到将问题切分到可解的时候再进行计算。 
  
时间复杂度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)
回溯法总结
 对于一个问题，如果用回溯法解题，可以抽象出这样的思路。
 
找到已知解，并将其作为解空间的叶子结点。 对于这个题来说，我们问的是从坐标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
这种方法也可以记录跳数。
 
以上代码都是白板乱写的，不一定能运行，大家看个思路就好。
 
本篇文章主要讲了DP和回溯法解题的区别。我觉得最主要的有以下几点。
 
理解解空间的构成，解空间中叶子节点是已知解，根节点是待解的问题。
回溯主要是自顶向下的求解过程，求解过程是从根节点到叶子结点。不断从根节点扩展出新的节点
动态规划主要是自底向上的求解过程，是从叶子结点（已知解）推导出根节点（未知解）的过程。
贪心则是一个局部最优的搜索过程。.
 
其实我觉得能看懂自顶向下和自底向上的分析过程就是最大的收获了
当我们学习了这些算法时，可能会疑惑：
为什么有些问题可以用分治算法解决，也可以用回溯算法解决？——全排列问题。
为什么有些问题可以用贪心算法解决，也可以用递归暴力解决，还可以用动态规划解决？——凑零钱问题。
为什么有些问题可以用递归解决，也可以用动态规划解决？——爬台阶问题。
其实，有些是切入的角度不同，有些只是效率不同。
递归是一种编程技巧，一种解决问题的思维方式；
分治算法和动态规划很大程度上是递归思想基础上的（虽
				
动态规划几篇文章已经完成，接下来看  优势、什么时候用……
我们前文经常说回溯算法和递归算法有点类似，有的问题如果实在想不出状态转移方程，尝试用回溯算法暴力解决也是一个聪明的策略，总比写不出来解法强。
那么，回溯算法和动态规划到底是啥关系？它俩都涉及递归，算法模板看起来还挺像的，都涉及做「选择」，真的酷似父与子。
那么，它俩具体有啥区别呢？回溯算法和动态规划之间，是否可能互相转化呢？
今天就用力扣第 494 题「目标和」来详细对比一下回溯算法和动态规划，真可谓群魔乱舞：
注意，给出的例子 nums .
				
贪心、回溯、分治、动态规划，确切地讲，应该是算法思想，并不是具体的算法，常用来知道我们设计具体的算法和编码等。上一章已经详细地分析过动态规划，接下来还是结合具体问题，感受一下这些算法是怎么工作的，是如何解决问题的，再问体体会这些算法的本质。我觉得比单纯记忆原理和定义更有价值。
1. 如何理解贪心算法？
假设我们有一个可以容纳100kg物品的袋子，可以装各种物品。有以下5种豆子，每种豆...
   分治法的设计思想是，将一个难以直接解决的大问题，分割成k个规模较小的子问题，这些子问题相互独立，且与原问题相同，然后各个击破，分而治之。
   分治法常常与递归结合使用：通过反复应用分治，可以使子问题与原问题类型一致而规模不断缩小，最终使子问题缩小到很容易求出其解，由此自然导致递归算法。
   根据分治法的分割原则，应把原问题分割成多少个子问题才比较适宜？每...
				
一、贪心法
贪心算法的定义：
贪心算法（也叫贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到全局最优解，得到的是局部最优解，关键是贪心策略的选择，不同的贪婪策略会导致得到差异非常大的结果。选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
解题的一般...
（1）回溯法 又称试探法
回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法；基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
适用场景：当遇到某一类问题时，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分
				
### 回答1：
分治策略是将一个复杂的问题分解成相互独立的子问题，然后递归地解决这些子问题，最后合并子问题的解得到原问题的解；动态规划是一种在求解复杂问题时寻求最优解的通用技术，它通过把原问题分解为相互依赖的子问题来实现；贪心算法是一种在每一步都采取在当前状态下最优的选择，从而希望导致结果是最优的算法；回溯法是一种试错法，它尝试分步解决一个复杂的问题，当它发现某一步无论如何也无法得到正确解决方案时，就会回溯到前一步并重新尝试。  
### 回答2：
分治策略、动态规划、贪心算法和回溯法都是解决问题的常用算法思想，它们在解决问题的方式和适用场景上有不同的特点。
分治策略是将问题分解为更小的子问题，在将子问题解决后进行合并得到整体问题的解。分治策略适用于问题可以分解为相同类型的子问题，并且子问题的解可以独立求解的情况。典型的应用包括快速排序和合并排序。
动态规划是一种以自底向上的方式逐步求解问题的优化方法。它将问题划分为重叠且相互依赖的子问题，使用一张表来记录子问题的解，通过解决子问题的最优解来解决整体问题。动态规划适用于满足最优子结构和无后效性的问题，常见的应用有背包问题和最短路径问题。
贪心算法是一种选择当前最优策略的方法，并且期望通过每一步的最优选择最终得到全局最优解。贪心算法通常没有全局优化的策略，而是通过选择局部最优解来进行推进。贪心算法适用于满足贪心选择性质和最优子结构的问题，例如霍夫曼编码和最小生成树问题。
回溯法是一种通过穷举所有可能的解来寻找问题解的方法。它采用试错的方式进行搜索，并在搜索过程中通过剪枝操作来减少不必要的计算。回溯法适用于问题解空间规模较小的情况，例如八皇后问题和0-1背包问题。
综上所述，分治策略通过分解子问题并合并解决整体问题，动态规划通过记录子问题的解来逐步求解整体问题，贪心算法通过每一步的最优选择来推进解决整体问题，回溯法通过穷举所有可能的解来寻找问题解。这四种算法思想各有不同的应用场景，根据问题的特点选择合适的算法可以更高效地解决问题。  
### 回答3：
分治策略、动态规划、贪心算法和回溯法是算法设计中常用的四种策略。它们具有各自独特的特点和应用场景。
分治策略是将问题划分为若干个规模较小且结构相似的子问题，通过递归地解决子问题，最后合并得到原问题的解。分治策略适用于问题可以分解为独立子问题，并且合并子问题的解不会产生冲突。典型应用如归并排序和快速排序。
动态规划是通过将问题划分为相互重叠的子问题，并求解子问题的解来求解原问题。动态规划通常适用于具有最优子结构的问题，可以通过空间换时间来提高效率。通过构建状态转移方程和建立递推关系，逐步计算得到最优解。典型应用如背包问题和最短路径问题。
贪心算法是一种每一步都选择当前状态下的最优解，以求得全局最优解的策略。它通过每一步的最优选择，局部地达到全局最优。贪心算法通常适用于问题具有贪心选择性质，即每个子问题都可以通过选取局部最优解而得到全局最优解。典型应用如霍夫曼编码和最小生成树算法。
回溯法是一种通过穷举所有可能的解，并逐步构建可行解的方法。它采用试错的方式，在每一步都通过选择一个可能的解决方案，然后进行尝试。若尝试失败，则回溯到上一步重新选择。回溯法适用于问题的解空间较小，且要求找出所有可能的解或满足特定条件的解。典型应用如八皇后问题和旅行商问题。
总之，分治策略、动态规划、贪心算法和回溯法都是解决问题的有效策略，通过合适的选择和设计，可以在不同的问题领域中获得最优解或满足特定条件的解。