动态规划、回溯法、贪心算法的区别与联系
以上三个算法的基本概念，网上有更多资料，这里就不详细展开了。接下来讲我在学习过程中遭遇的问题。在实际运用这些算法解题的时候，经常会看到一些很奇怪的名词，比如解空间、自顶向下解法、自底向上解法等等。那么这些词到底代表的是什么含义呢？接下来通过一些具体的例子和图来展示。
举例 斐波那契数列问题问题描述
斐波那契数列是通过"递归"定义的，通过这个递归关系式，我们可以知道斐波那契数列中任意一个位置的数值。给你一个数字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)的时候，我们才能够根据已有的条件得到答案，然后往上回推。
代码示意如下
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]
总结
上文主要描述了解题的时候，回溯法和动态规划之间的区别。主要有以下几点。
问题链接
问题描述：
这道题目是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)
回溯法总结
对于一个问题，如果用回溯法解题，可以抽象出这样的思路。
回溯优化
对于整个回溯过程，普遍存在的问题是会存在着大量计算。比较好的优化思路是使用一个数组去记录已经得到的解。这样下次查询的时候，先判断一下是否已经解过了就好了。这个思路，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 len(a)-1
这种方法也可以记录跳数。
以上代码都是白板乱写的，不一定能运行，大家看个思路就好。
总结本篇文章主要讲了DP和回溯法解题的区别。我觉得最主要的有以下几点。
理解解空间的构成，解空间中叶子节点是已知解，根节点是待解的问题。 回溯主要是自顶向下的求解过程，求解过程是从根节点到叶子结点。不断从根节点扩展出新的节点 动态规划主要是自底向上的求解过程，是从叶子结点（已知解）推导出根节点（未知解）的过程。 贪心则是一个局部最优的搜索过程。.其实我觉得能看懂自顶向下和自底向上的分析过程就是最大的收获了
作者：逃离地球的小小呆
