分治

“分治”也就是分而治之，也就是说，分治法将原问题划分成若干个规模较小而结构与原问题相同或相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到为原问题的解。上面的定义体现出分治法的三个步骤：

分解：将原问题分解为若干和原问题拥有相同或相似结构的子问题。
解决：递归求解所有子问题。如果存在子问题的规模小到可以直接解决，就直接解决它。
合并：将子问题的解合并为原问题的解。

需要注意，分治法分解出的子问题应当是相互独立、没有交叉的。如果存在两个子问题有相交部分，那么不应当使用分治法解决。
从广义上来说，分治法分解成的子问题个数只要大于 0 即可。但是从严格的定义上讲，一般把子问题个数为 1 的情况称为减治 (decrease and conquer)，而把子问题个数大于 1 的情况称为分治，不过通常情况下不必在意这种区别。另外，分治法作为一种算法思想，既可以使用递归的手段去实现，也可以通过非递归的手段去实现，可以视具体情况而定，一般来说，使用递归实现较为容易。

递归

斐波那契数列

写递归其实找到递归的表达式就好了，但是难就难在找这个递归表达式，需要多多做题，做多了熟练了，就容易找了，通常递归表达式可能如下：

如经典的斐波那契数列：

$\begin{equation} \left\{ \begin{array}{lr} F(n)=1, & n=0,\ 1\\ F(n)=F(n-1)+F(n-2), & n \geq 2 \end{array} \right. \end{equation}$

写成代码如下所示：

def Fibonacci(n):
    if n == 0 or n == 1:
        return 1
    else:
        return Fibonacci(n - 1) + Fibonacci(n - 2)

res = Fibonacci(10)
print("计算10的结果为：" + str(res))

运行结果如下：

1	计算10的结果为：89

书里给出计算 n == 4 的递归图：

其实上述求解斐波那契数列的方法，就是使用递归实现分治法的一个简单例子。

对于给定的正整数 n，把求解 F(n) 的问题分解为求解 F(n - 1) 和 F(n - 2) 两个问题。而对于 F(0) = F(1) = 1 是 n 很小的问题，可以直接解决，递归式 F(n) = F(n - 1) + F(n - 2) 则是子问题解的合并。

那么通过上述例子可以知道，想要实现一个递归函数，需要如下两个东西：①递归边界 ②递归式。

递归边界就是返回最简单底层的结果；
递归式就是用来减少数据规模并向下一层递归；

可以画出递归图来便于理解递归解法。实现递归解法的关键就在于这两点。

斐波那契数列的优化

其实通过递归图可以看出，在递归的过程中，有很多重复的步骤，如计算了很多次的 F(2)、F(3)，这个时候就会浪费很多时间，那么应该如何优化呢？一个很简单的思路：采用记忆化方案，用字典保存每次新计算的结果，如果需要的结果之前已经计算过了，那么就直接拿过来用，这样可以减少十分多的重复步骤，优化代码如下：

"""
字典优化解法
"""
def fibonacci_memo(n, memo):
    if n in memo:
        return memo[n]

    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

memo = dict()
memo[0] = 1
memo[1] = 1
# 记录开始时间
start_time = time.perf_counter()
n = 500
res = fibonacci_memo(n, memo)
# 记录结束时间
end_time = time.perf_counter()
print(f"计算{n}的结果为：" + str(res))
print("耗时为：", str(end_time - start_time), " 毫秒")

同时运行两个代码，并且打印出运行耗时：

计算10次的结果为：89
耗时为： 1.219999830937013e-05  毫秒
计算500的结果为：225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626
耗时为： 0.00014370000280905515  毫秒

可以看到，字典优化后的代码时间复杂度极优越，从 10 到 500，耗时却少上千倍。

所以在使用递归解法的时候，尽量使用记忆化方案，可以极大的减少超时情况。

全排列

全排列问题就是对于给定的 n 个整数能形成的所有排列。

那么就可以把它分解为若干个子问题：以 1 开头的全排列、以 2 开头的全排列、以 3 开头的全排列…以 n 开头的全排列。

那么可以这么做：使用数组 P 存放当前的排列，然后设置一个散列数组 hash_table，当整数 x 在数组 P 里的时候，hash_table[x] 为 True。

接下来按顺序在数组 P 中的第 1 位到第 n 位填入数字。我们假设已经填好了 P[1] - P[index - 1]，现在准备填入 P[index]，那么需要枚举 1 ~ n，如果当前枚举的数字 x 还没在 P[1] ~ P[index - 1]中（hash_table[x] == False），就把他填入到 P[index]，同时 hash_table[x] = True，然后去处理 P 的第 index + 1 位（进行递归）；递归完成时，将 hash_table[x] 还原为 False，接着让 P[index] 填下一个数字。

这里的递归边界就是：index 达到 n + 1，说明 1 ~ n 位已经填好了。这时就可以输出 P 了，表示生成了一个排列。

代码如下：

def generate_p(index, n, p, hash_table):
    if index == n + 1:  # 递归边界，已经处理完排列的 1 ~ n 位
        print(p)  # 输出当前排列
        return

    for x in range(1, n + 1):  # 枚举 1 ~ n，试图将 x 填入 P[index]
        if not hash_table[x]:  # 如果 x 不在 P[1] ~ P[index-1] 中
            p[index] = x  # 令 P 的第 index 位为 x，即把 x 加入当前排列
            hash_table[x] = True  # 记 x 已在 P 中
            generate_p(index + 1, n, p, hash_table)  # 处理排列的第 index + 1 号位
            hash_table[x] = False  # 还原状态


def main():
    n = 3  # 欲输出 1 ~ 3 的全排列
    p = [0] * (n + 1)  # 创建排列数组
    hash_table = [False] * (n + 1)  # 创建哈希表
    generate_p(1, n, p, hash_table)  # 从 P[1] 开始填


if __name__ == "__main__":
    main()

n 皇后

n 皇后问题是指在一个 n * n 的国际象棋棋盘上放置 n 个皇后，使得这个皇后两两均不在同一行、同一列、同一条对角线上，求合法的方案数。

这个问题如果采用组合数的方式来枚举的话，也就是从 $ n^2 $ 个位置里选择 n 个位置，自然需要 $ C_{n×n}^n $ 的枚举量，这自然是无法接受的。

现在我们换一个思路，因为每行每列只能放一个皇后，如果把 n 列皇后所在的行号依次写出来，那么就是一个 1 ~ n 的全排列，于是，这里我们只需要枚举 1 ~ n 的所有排列，查看每个配列对应的放置方案是否合法，统计合法的方案就好了。