1、递归（技巧）

通过调用自身程序的方法称为递归，满足递归的三个条件

• 一个问题的解可以分解为几个子问题的解
• 这个问题与分解之后额度子问题，除了数据规模不同，求解思路完全一样

• 存在递归终止条件

注意：堆栈溢出

递归调试方法：1、打印日志发现，递归值 2、结合条件断点进行调试

2、贪心算法 Greedy Algorithm

1、理解

每次选择当前情况下的最优解，直到结束。

该方法，可能会导致最终的结果不是整体的最优解。

2、分糖果

有 m 个糖果和 n 个孩子。每个糖果大小不等，这 m 个糖果的大小分别是 s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。

用贪心算法来解决。对于一个孩子来说，如果小的糖果可以满足，我们就没必要用更大的糖果，这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面，对糖果大小需求小的孩子更容易被满足，所以，我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们期望值的贡献是一样的。

我们每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。

3、区间覆盖

假设我们有 n 个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。我们从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？

解决：

假设这 n 个区间中最左端点是 lmin，最右端点是 rmax。这个问题就相当于，我们选择几个不相交的区间，从左到右将[lmin, rmax]覆盖上。我们按照起始端点从小到大的顺序对这 n 个区间排序。

我们每次选择的时候，左端点跟前面的已经覆盖的区间不重合的，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间。这实际上就是一种贪心的选择方法。

4、霍夫曼编码

假设我有一个包含 1000 个字符的文件，每个字符占 1 个 byte（1byte=8bits），存储这 1000 个字符就一共需要 8000bits，那有没有更加节省空间的存储方式呢？

通过统计分析发现，这 1000 个字符中只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f。

霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。霍夫曼编码试图用这种不等长的编码方法，来进一步增加压缩的效率。如何给不同频率的字符选择不同长度的编码呢？根据贪心的思想，我们可以把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。

假设这 6 个字符出现的频率从高到低依次是 a、b、c、d、e、f。我们把它们编码下面这个样子，任何一个字符的编码都不是另一个的前缀，在解压缩的时候，我们每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。经过这种编码压缩之后，这 1000 个字符只需要 2100bits 就可以了。

如何根据字符出现频率的不同，给不同的字符进行不同长度的编码呢？

把每个字符看作一个节点，并且附带着把频率放到优先级队列中。我们从队列中取出频率最小的两个节点 A、B，然后新建一个节点 C，把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点。最后再把 C 节点放入到优先级队列中。重复这个过程，直到队列中没有数据。

给每一条边加上画一个权值，指向左子节点的边我们统统标记为 0，指向右子节点的边，我们统统标记为 1，那从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。

3、分治算法 Divide and Conquer

分而治之

分治算法是一种处理问题的思想，递归是一种编程技巧。

分治算法解决问题，需满足以下条件：

• 原问题与分解成的小问题具有相同的模式
• 原问题分解成的子问题可以独立求解，子问题之间没有相关性

• 具有分解终止条件，也就是说，当问题足够小的时候，可以直接求解
• 可以将子问题合并为原问题，且合并复杂度不高。

1、求出一组数据的有序对个数或逆序对个数

假设我们有 n 个数据，我们期望数据从小到大排列，那完全有序的数据的有序度就是 n(n-1)/2，逆序度等于 0；

采用分治的思想，借助在归并排序的时候，其中 将两个有序的小数组 ，合并成一个有序的数组时，便可以计算着两个小数组的逆序对个数。

inversion_num = 0

def merge_sort_counting(nums, start, end):
    if start >= end:
        return
    
    mid = (start+end) // 2
    # 拆分到最小数组
    merge_sort_counting(nums, start, mid)
    merge_sort_counting(nums, mid+1, start)
    # 合并
    merge(nums, start, mid, end)
    
    
def merge(nums, start, mid, end)
	global inversion_num
    left = start
    right = mid + 1
    tmp = []
    while left <= mid and right <= end:
        if nums[left] <= nums[right]:
            inversion_num += right - mid - 1
            tmp.append(nums[left])
            left += 1
        else:
            tmp.append(nums[right])
            right += 1
    while left <= mid:
        inversion_num += end - mid
        tmp.append(nums[left])
        left += 1
    while rigth <= end:
        tmp.append(nums[right])
        right += 1
    nums[start:end+1] = tmp

4、回溯算法 Backtracking Algorithm

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

1、八皇后问题

有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。

把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。

def eight_queens():
    solutions = []
    def backtracking(queens_at_cloumn, index_sums, index_diffs):
        row = len(queens_at_cloumn)
        if row == 8:
            solutions.append(queens_at_cloumn)
            return
        for col in range(8):
            if col in queens_at_cloumn or row+col in index_sums or row-col in index_diffs:
                continue
            backtracking(queens_at_column + [col], index_sums + [row + col], index_diffs + [row - col])
    backtracking([], [], [])
    print(*(" " + " ".join("*" * i + "Q" + "*" * (8 - i - 1) + "\n" for i in solution) for solution in solutions), sep="\n")

5、动态规划 Dynamic Programming

把问题分解为多个阶段，每个阶段对应一个决策。记录每一个阶段可达的状态集合（去重），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。

1、一个模型三个特征

适合动态规划解决的问题，需要满足一个模型三个特征。

1、模型：多阶段决策最优解模型

一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

2、特征：最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。

3、特征：无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

4、重复子问题

这个概念比较好理解。前面一节，我已经多次提过。如果用一句话概括一下，那就是，不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

2、解题思路

1、状态转移表法

回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递归关系填表-将填表过程翻译成代码

2、状态转移方程法

找最优子结构-写状态转移方程-将状态转移方程翻译成代码

1、0-1背包问题

有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

假设背包的最大承载重量是 9。我们有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3。

 

将整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策完之后，背包中的物品的重量会有多种情况。也就是说，会达到多种不同状态，对应到递归树中，就是有很多不同的节点。

将每一层重复的节点合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过 w 个（w表示背包的承载重量），也就是假设的 9，这样可以避免没层状态个数的指数级增长。

使用一个二维数组 states[n][w+1] ，来记录每层可以达到的不同状态。

第 0 个（下标从0开始编号）物品的重量是2，要么装入背包，要么不装入背包，决策完之后，会对应背包两种状态，背包中物品的总重量是 0 或者 2。使用 states[0][0] = true 和 states[0][2] = true 来表示这两种状态。

第 1 个物品的重量也是 2，基于上一个操作后的状态，在这个物品决策完之后，不同的状态会有 3 个，分别是 0(0+0)，2(2+0 or 0+2)，4(2+2)，使用states[1][0] = true，states[1][2] = true，states[1][4] = true来表示这三种状态。

以此类推，直到所有物品结束，整个 states 状态数组已经计算完成。

这个时候只需要在最后一层，找到一个值为 true 的最接近 w 的值，就是物品背包总重量的最大值。

为了降低空间复杂度，这里将二维数组优化为一维数组

注意：第二个for循环需要倒序遍历，否则会出现for循环重复计算的问题。

如果从前往后循环，比如states[5] = 0,i = 1且重量为4,则j = 1时states[j + items[i]] = states[1 + 4] = states[5] = 1，上一层的临时结果在还未被访问时就被覆盖，信息丢失，故不可以从前往后计算

def bag(items_info, capacity):
    """
    固定容量的背包，计算能装进背包的物品组合的最大重量
    :param items_info: 每个物品的重量
    :param capacity: 背包容量
    :return: 最大装载重量
    """
    n = len(items_info)
    states = [-1] * (capacity+1)
    states[0] = 1
    if states[0] <= capacity:
        states[items_info[0]] = 1
    
    for i in range(1, n):
        x = capacity-items_info[i]
        for j in range(x, -1, -1):
            if states[j] == 1:
                states[j+items_info[i]] = 1

    for i in range(capacity, -1, -1):
        if states[i] == 1:
            return i

2、0-1背包问题升级版

上面只涉及背包重量和物品重量。我们现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢？

from typing import List

def knapsack01(weights: List[int], values: List[int], capacity: int) -> int:
    # Denote the state as (i, c), where i is the stage number,
    # and c is the capacity available. Denote f(i, c) to be the
    # maximum value when the capacity available is c, and Item 0
    # to Item i-1 are to be packed.
    # The goal is to find f(n-1, W), where W is the total capacity.
    # Then the DP functional equation is:
    #   f(i, c) = max(xᵢvᵢ + f(i-1, c-xᵢwᵢ)), xᵢ ∈ D, i ≥ 0,
    #   f(-1, c) = 0, 0 ≤ c ≤ W,
    # where
    #                  /  {0},    if wᵢ > c
    #   D = D(i, c) = 
    #                  \  {0, 1}, if wᵢ ≤ c

    prev = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        prev = [c >= w and max(prev[c], prev[c-w] + v) for c in range(capacity + 1)]
    return prev[-1]


if __name__ == "__main__":
    # To find the maximum weight that can be packed,
    # set values equal to the weights
    print(knapsack01([2, 2, 4, 6, 3], [2, 2, 4, 6, 3], 9))