今天就简单来谈谈这几者之间的关联和区别
递归
一句话，我认为递归的本质就是将原问题拆分成具有相同性质的子问题。
递归的特点：
- 1、子问题拆分方程式，比如：f(n) = f(n-1) * n
- 2、终止条件：也就是子问题无法再进一步拆分时，这时可以直接求出解，退出递归。
一个问题能否使用递归求解，就看能不能满足上面两个特征
以数值的整数次方为例
通过分析，我们很容易的知道上面这道题是非常符合递归特征的
- 1、子问题拆分方程式：
f(x, n) = f(x, n-1) * x - 2、终止条件：
if n < 2: return x
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
# 因为题目n有可能为负数，因此这里需要判断
if n == 0:
return 1
if n > 0:
return self.abs_pow(x, n)
if n < 0:
abs_val = self.abs_pow(x, -n)
return 1 / abs_val
def abs_pow(self, x, n):
# 该递归函数只处理n为正数，n为负数时，由调用方反除一下即可。
if n < 2:
return x
rst = self.abs_pow(x, n-1)
return x * rst因为递归的调用栈时有深度限制的，因此这道题是没法AC的
有时候我们会遇到很多这样的情况，那么怎么解决调用深度的问题呢，很容易想到递归的兄弟迭代。
迭代
我们知道递归和迭代其实是天生一对的，本质是一样的，迭代只是我们自己模拟了递归的调用栈而已，因此迭代一般会用到栈这样的数据结构
当然由于这道题比较简单，用不到栈，只是一个数的叠乘而已
def abs_pow(self, x, n):
rst = 1
while n > 0:
rst *= x
n -= 1
return rst递归和迭代在二叉树用的非常多，二叉树基本天生就跟递归一起的，因为思路简单，符合人们的正常思维，只要有递归的地方，都可用转换为迭代，大家可以自己使用二叉树的题目来练习练习递归和迭代。
分治
其实，我认为递归算法从本质上来说都是分治算法，无非就是有些问题递归需要将原问题分解成多个子问题，而有的只需要分解成一个子问题，因此有的人将前面那种情况称作分治，将后面那种情况称作递归。
之前说过，递归跟迭代是一一对应的，因此分治有两种解法: 递归和迭代
分治算法的思想：
- 1、数学归纳法：只要出现可以用数学归纳公式来表示的大规模问题，第一反应就应该想到分治算法，通过特定的函数参数安排，一定可以用同一个函数来表述不同规模的问题，套用递归结构，可迅速解决问题！
- 2、不一定使用递归结构：递归结构是循环结构的一种，也是分治思想应用最多的一种程序结构，但是不一定要使用它！关键在于能够写出递归公式以及是否有必要使用递归算法。
因此可以知道，分治是一种算法思想，递归是一种技术手段。
分治算法的特征：
- 1、分解：将原问题拆分成若干个子问题
- 2、求解子问题：也就是终止条件
- 3、合并：将各个子问题的解合并，形成原问题的解
下面以斐波那契数列为例：
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 0:
return 0
# 备忘录
memo = [0] * (n+1)
return self.f(n, memo)
def f(self, n, memo):
# 终止条件
if n in [1, 2]:
return 1
if memo[n] != 0:
return memo[n]
# 分解
n1 = self.f(n-1, memo)
n2 = self.f(n-2, memo)
# 合并
memo[n] = (n1 + n2) % 1000000007
return memo[n]
注：分治算法一般体现在归并排序和快速排序里面
从这道题可以看出：
- 1、
在求解该问题的时候，有很多重复的子问题，这样会导致非常低效，于是我们加了缓存，也就是带备忘录的递归解法， - 2、整个解法是
自顶向下的，通过画递归树就很容易的看出来。比如f(20)，向下逐渐分解，知道f(1)和f(2)，然后触底返回。
回溯
回溯其实类似于DFS搜索算法，以二叉树为例：
- 1、从根节点出发
- 2、随便选择一个子节点并达到该子节点，并
标记该节点 - 3、然后从该子节点又随便选择一个子节点并到达该子节点，直到到达叶子节点
- 4、此时我们已经完整的做了一次选择，但是我们发现，在根节点到叶子节点的路径中，我们还有很多选择可以做。因此，
我们需要从叶子节点往上一层层的返回，每返回一个节点，都选择一个之前没有走过的节点继续走下去，也就是重复2/3/4步骤，直到遍历完整个二叉树。
说了这么多，那么回溯跟上面讲的几个算法有什么联系呢：
我们来看下回溯算法的几个特征就知道了
回溯算法的特征：
- 1、深度优先遍历dfs：回溯算法一般采用dfs求解，因此满足递归的一般特征
- 2、子集：回溯题目一般都要求求解所有的最优解，因此，dfs的
终止条件就是判断是否得到了一个最优解，然后直接返回。 - 3、遍历空间集：在每一轮dfs中都需要遍历空间集，根据题目性质，有的需要
从0开始，有的需要从当前位置开始。 - 4、剪枝：在遍历空间集的时候，需要
优先将不符合条件的去除掉，不然会做很多无用的递归调用，导致超时。 - 5、加入元素：遍历空间集的时候，加入每一个元素，然后再dfs
- 6、移除元素：当一轮dfs达到终止条件结束的时候，说明当前选择已经完成，需要
返回到上一轮做其他选择，因此需要将上一轮选择时加入的元素删除掉。
这很抽象，我们以组合总和为例
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
rst = []
# 先对列表排序，便于剪枝
candidates.sort()
self.dfs(rst, [], candidates, target, 0)
return rst
def dfs(self, rst, sub_rst, candidates, target, start):
# 终止条件：一般就是判断是否找到了一个最优解
if sum(sub_rst) == target:
rst.append(sub_rst[:])
return
# 遍历空间集：从当前位置出发
for index in range(start, len(candidates)):
# 加入每一个元素
sub_rst.append(candidates[index])
# 判断是否超过了总和，是则直接返回（因为前面我们已经排过序了）
if sum(sub_rst) > target:
sub_rst.pop()
break
# 开始dfs下一轮：因为这道题目要求每一个数字可以重复使用，因此下一轮的start也是当前位置
# 有的题目要求不能重复使用，那么这里的index应该改为 index+1
self.dfs(rst, sub_rst, candidates, target, index)
# 已经完成一轮dfs，开始返回上一轮做其他选择，先将本轮的选择去掉
sub_rst.pop()动态规划
动态规划也简称dp，动态规划的定义是什么，我也不知道，各有各的理解吧
动态规划的特征：
- 1、最优子结构：在自下而上的递推过程中，我们求得的每个子问题一定是全局最优解，既然它分解的子问题是全局最优解，那么依赖于它们解的原问题自然也是全局最优解。
- 2、重叠子问题：在求解原问题的时候，我们往往需要依赖其子问题，子问题依赖其子子问题，甚至可能同时依赖多个子问题，因此子问题之间是有重叠关系的。
- 3、状态初始化：因为动态规划是依赖子问题的，因此需要先初始化已知状态，从而才能自下而上的递推到原问题得解。
- 4、遍历状态集：首先根据需要求解的结果来确定状态集，然后遍历状态集，更新状态dp
- 5、状态转移方程：也就是每一级子问题之间的关系式。
下面以最长回文子串为例
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
len_s = len(s)
if len_s < 2:
return s
# 因为是判断子串，根据子串的性质s[i:j]，因此必然涉及到两层循环，也就需要定义二维数组dp
# 状态初始化：默认为True，可以省去很多计算
dp = [[True for _ in range(len_s)] for _ in range(len_s)]
max_len = 0
start = 0
# 状态转移方程：表示i到j的子串是否是回文子串
# dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])
# 遍历状态集：因为需要知道j-1，因此j需要从1开始
for j in range(1, len_s):
# 因为是子串，i一定是要小于j
for i in range(j):
if s[i] == s[j]:
# 如果收尾字符相等，那么直接取决于去掉该收尾的子串
dp[i][j] = dp[i+1][j-1]
else:
# 如果不相等，不管子串如何，肯定不是回文
dp[i][j] = False
# 更新最大长度
if dp[i][j] and max_len < j - i:
max_len = j - i
start = i
return s[start:start+max_len+1]从这道题可以看出：
整个解法是自底向上的，也就是先得到dp[0][0]，然后逐渐的扩大范围，最终得到dp[0][n]
这跟前面递归和分治时提到的自顶向下，形成对比。
贪心
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。
贪心算法的特征：
- 1、最优子结构：贪心算法也是将原问题分解成多个性质相同的子问题，每个问题都是局部最优。
- 2、贪心选择性质：在做贪心选择时，我们直接做出当前子问题中看起来最优的解，这也是贪心算法和动态规划的不同之处。
- 3、遍历状态集：遍历状态集，做出局部最优选择，更新结果。
- 4、无后效性：某个状态以后的过程不会影响以前的状态，只与当前状态有关。
下面以为例
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums:
return False
len_nums = len(nums)
max_pos = 0
# 遍历状态集
for i in range(len_nums):
if i > max_pos:
return False
# 对每一个状态选择都做局部最优解
max_pos = max(max_pos, i + nums[i])
if max_pos >= len_nums-1:
return True
return False这里提下
涉及到贪心算法的核心性质：
只适用于求解可行解，不适用于求最值以及所有解
后记
《算法之道》对其中的三种算法进行了归纳总结，如下表所示：
| - | 标准分治 | 动态规划 | 贪心算法 |
|---|---|---|---|
| 适用类型 | 通用问题 | 优化问题 | 优化问题 |
| 子问题结构 | 每个子问题不同 | 很多子问题重复 | 只有一个子问题 |
| 最优子结构 | 不需要 | 必须满足 | 必须满足 |
| 子问题数 | 全部子问题都要解决 | 全部子问题都要解决 | 只要解决一个子问题 |
| 子问题在最优解里 | 全部 | 部分 | 部分 |
| 选择与求解次序 | 先选择后解决子问题 | 先解决子问题后选择 | 先选择后解决子问题 |
评论 (19)
