##### 二

- [x] 递归
  - [x] 整数划分
  
  ```python
  def integer_partition(n, m):
      """将整数 n 分成若干个不超过 m 的整数之和"""
      # 如果 n 刚好 == 0 说明刚好被分完, 划分数 + 1
      if n == 0:
          return 1
      
      # 如果 n < 0 或者 m <= 0, 则没有合法的划分方法
      # n < 0 是因为之前用来划分的数太大了, 原数不够划分
      # m <= 0 是因为之前划分数太小, 原数还没划分完
      if n < 0 or m <= 0:
          return 0
      
      # 递归调用, 分成两种情况:
      # 1. 使用 m 来划分, 那么剩下的数就要减去 m, 即 n - m
      # 2. 不使用 m 来划分, 之后尝试使用更小的数来划分, 即 m - 1, 因为不使用 m 来划分, 所以原来的数 n 不变
      return integer_partition(n - m, m) + integer_partition(n, m - 1)
  ```
  
  
  
  - [x] 汉诺塔
  
  ```python
  def hanoi(n, source, target, mid):
      """将 n 个盘子从 source 移动到 target, 使用 mid 作为中间辅助柱子"""
      if n == 1:
          # 如果只有一个盘子, 就可以直接从 source 移动到target 无需辅助
          print(f"移动盘子 {n} 从 {source} 到 {target}")
      else:
          # 就以两个最简单的两个盘子举例, 来写出递归 (一定不需要深想, 相信递归函数能够做好)
          # quote: 明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节， 否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。
          # https://oi-wiki.org/basic/divide-and-conquer/
          
          # 如果只有两个盘子, 就先要把上面的一个盘子先移动到 mid 也就是辅助柱子上
          hanoi(n - 1, source, mid, target)   # 此时 mid 作为目的地, 所以 target 变量填 mid
          # 然后把最底下最大的盘子移动到 target 上
          print(f"移动盘子 {n} 从 {source} 到 {target}")
          # 最后把 mid 上的盘子移动到 target 上
          hanoi(n - 1, mid, target, source)
  ```
  
  
  
- [ ] 分治
  - [x] 二分
  
  ```python
  def binary_search(arr, key, start, end):
      ret = -1
      mid = -1
      while (start <= end): # 还在搜索范围内就继续搜索
          mid  = (start + end) // 2 # 取中间位置
          if arr[mid] < key:
              start = mid + 1
          elif arr[mid] > key:
              end = mid - 1
          else:
              ret = mid
              break
      return ret
  ```
  
  
  
  - [x] 快排
  
  ```python
  def quick_sort(arr, front, end):
      if front >= end:
          return  # 当分到每组只有一个元素时, 说明已经有序, 返回
      pivot = arr[front]  # 选择当前组的第一个元素为基准元素
  
      low = front # 从基准元素的下一个位置开始
      high = end
  
      while low < high:
          # 从右向左找到第一个小于基准的元素
          while low < high and arr[high] >= pivot:
              high -= 1
          arr[low] = arr[high] # 将小于基准的元素放到左边 (因为基准元素已经被记录下来了 所以可以被覆盖)
  
          # 从左向右找到第一个大于基准的元素
          while low < high and arr[low] <= pivot:
              low += 1
          arr[high] = arr[low]
  
      arr[low] = pivot  # 将基准元素放到正确的位置 (此时 low == high, low 左边的元素都小于基准元素, 右边的元素都大于基准元素)
      quick_sort(arr, front, low - 1)  # 对基准元素左边的部分进行快速排序
      quick_sort(arr, low + 1, end)  # 对基准元素右边的部分进行快速排序   (在中间的基准元素已经被放到正确的位置了, 所以不需要再处理)
  ```
  
  
  
  - [x] 归并
  
  ```python
  def merge(a, b):
      i, j = 0, 0 # i, j 分别为 a, b 的索引
      c = []  # c 为合并之后的数组
      while i < len(a) and j < len(b):
          if a[i] < b[j]:
              c.append(a[i]) # 让较小的元素先加入 c
              i += 1
          else:
              c.append(b[j])
              j += 1
      
      # 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
      c.extend(a[i:])  # 将 a 中剩余的元素加入 c
      c.extend(b[j:])  # 将 b 中剩余的元素加入 c
  
      return c
  
  def merge_sort(arr, low, high):
      if high - low <= 1:
          return
      
      mid = (low + high) // 2 # 将数组分成两半
      merge_sort(arr, low, mid)  # 对左半部分进行归并排序 [low, mid)
      merge_sort(arr, mid, high)  # 对右半部分进行归并排序 [mid, high)
  
      # 合并两半
      arr[low:high] = merge(arr[low:mid], arr[mid:high])  # 将两半合并到原数组中
  ```
  
  
  
  - [ ] Stassen矩阵乘法

##### 三

- [x] 矩阵链乘

[【算法设计】 动态规划 矩阵链相乘问题](https://www.bilibili.com/video/BV16t4y1R7fJ)
$$
m[i, j] = 
\begin{cases}
0, & \text{if } i = j \\
\min\limits_{i \leq k < j} \left\{ m[i, k] + m[k+1, j] + p_{i-1}p_kp_j \right\}, & \text{if } i < j
\end{cases}
$$

- [ ] 最长公共子序列
- [ ] 01背包



##### 四

- [ ] 活动安排问题
- [ ] 最优装载
- [ ] 单源最短路
- [ ] 最小生成树



##### 五

- [ ] DFS
- [ ] BFS
- [ ] 回溯法
  - [ ] 01背包
  - [ ] 旅行商问题
  - [ ] N皇后问题
- [ ] 分支限界
  - [ ] 队列式
  - [ ] 优先队列式
- [ ] 分支限界问题
  - [ ] 单源最短路
  - [ ] 任务调度问题
  - [ ] 旅行商问题