1 分治与递归

1.1 阶乘函数

image-20220320161510908

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//阶乘函数
# include <iostream>
using namespace std;
int factorial(int n) 
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}
int main()
{   
    int n;
    cin >> n;
    cout << factorial(n) << endl;
    return 0;
}

1.2 Fibonacci数列

image-20220320161403851

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Fibonacci数列
# include<iostream>
using namespace std;
int fibonacci(int n){
    if (n <= 1)
        return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}
int main(){
    int n;
    cin >> n;
    cout << fibonacci(n) << endl;
    return 0;
}

1.3 全排列问题

image-20220320161642543

思路：

  • 定义函数perm(int list[], int k, int m)表示获取list[k:m]的全排列。
  • 递归条件：
    • 当n=1时，全排列只有一种，即为它本身。
    • 当n>1时，可以依次将每一个数作为前缀，然后对后续n-1个数进行全排列。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 全排列
# include<iostream>
using namespace std;
void swap(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}
//产生list[k:m]的全排列
int perm(int list[], int k, int m){
    if (k == m) { //只剩一个元素
        for(int i =0;i <=m;i++){
            cout << list[i];
        }
        cout << endl;
    }
    else {
        //还有多个元素，递归产生排列
        for (int i = k; i<=m; i++) { 
            //k到m的元素依次作为前缀,生成剩余数的全排列
            swap(list[k], list[i]);
            perm(list, k+1, m);
            swap(list[k], list[i]);
        }
    }
}
int main(){
    int a[] = {1,2,3};
    perm(a, 0, 2);
    return 0;
}

1.4 整数划分问题

image-20220320162315684

image-20220320162341988

（1）递归解法

思路：

对于$q(n,m)$：

  • 当n=1,m=1时，整数划分只有一种结果

  • 当n<m时，q(n,m)等价于q(n,n)

  • 当n=m时，共有1+q(n,m-1)中划分结果：

    • 整数划分中包含m，则只有一种划分结果，即{m}
    • 整数划分中不包含m，则意味着划分中的最大整数位m-1，即需递归解决q(n,m-1)

  • 当n>m时，共有q(n-m,m)+q(n,m-1)中划分结果

    • 整数划分中包含m，即划分为{m,{..}，这其中除了m外，其余部分可以看成对n-m继续进行划分，最大值可能为m,需递归解决q(n-m,m)
    • 整数划分中不包含m，即划分结果中最大为m-1，递归解决q(n,m-1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//整数划分问题（递归解法） https://developer.aliyun.com/article/445250
//TODO: 动态规划解法
#include <iostream>
using namespace std;
int q(int n, int m){
    if (n == 1 || m == 1) {
        return 1;
    }
    if (n < m) {
        // 最大的划分不会超过n，所以等价于q(n, n)
        return q(n, n); 
    }
    if (n == m) {
        // (1)划分中包含m，则划分就为{m}，只有一个数
        // (2)划分中不包含m，则划分中的最大数只能为m-1，即递归划分为q(n,m-1)个数
        return 1 + q(n, m - 1);
    }
    if (n > m) {
        // (1) 划分中包含m，即{m, {...}}, 其中除了m外，其余的看成对n-m继续进行划分，最大值可能为m, 即为q(n, m)
        // (2) 划分中不包含m，即划分中的所有数都要小于m，即看成为q(n,m-1)
        return q(n - m, m) + q(n, m - 1);
    }
}

int main(int argc, char const *argv[])
{
    int n,m;
    cin >> n >> m;
    cout << q(n,m) << endl;
    return 0;
}

（2）动态规划解法

TODO

1.5 棋盘覆盖问题

image-20220320200745108

image-20220320200807568

思路：

  • 分治法将棋盘划分为四个区域，从而得到四个子问题进行解决。

  • 特殊方格必然位于四个区域中的其中一个，但是另外三个区域则没有特殊方格，导致了子问题不相同。因此，可以假设先用一个L型骨牌放在四个区域的交界处当作特殊方格，从而使每一个区域内都存在一个特殊方格，如下图所示：

    image-20220320201130769

  • 通过这样的分割和假设，棋盘分割问题就可以转化为四个1/4规模的子问题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//棋盘覆盖问题
#include <cstdio>
#include <vector>

int tile = 0;              // L型骨牌的编号
int Board[100][100] = {0}; //存放棋盘

void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
    if (size == 1)
        return;
    int t = ++tile;   //表示L型骨牌的编号
    int s = size / 2; //划分区域

    if (dr < tr + s && dc < tc + s) //如果特殊方格在左上区域
    {
        ChessBoard(tr, tc, dr, dc, s); //解决左上区域的子问题
    }
    else //如果特殊方格不在在左上区域
    {
        Board[tr + s - 1][tc + s - 1] = t;             //用L型骨牌在该区域右下角放置一个特殊方格
        ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s); //有特殊方格后则可以继续解决该子问题
    }

    if (dr < tr + s && dc >= tc + s) //如果特殊方格在右上区域
    {
        ChessBoard(tr, tc + s, dr, dc, s); //解决右上区域的子问题
    }
    else //如果特殊方格不在右上区域
    {
        Board[tr + s - 1][tc + s] = t;                 //用L型骨牌在该区域左下角放置一个特殊方格
        ChessBoard(tr, tc + s, tr + s - 1, tc + s, s); //有特殊方格后则可以继续解决该子问题
    }

    if (dr >= tr + s && dc < tc + s) //如果特殊方格在左下区域
    {
        ChessBoard(tr + s, tc, dr, dc, s); //解决左下区域的子问题
    }
    else //如果特殊方格不在左下区域
    {
        Board[tr + s][tc + s - 1] = t;                 //用L型骨牌在该区域右上角放置一个特殊方格
        ChessBoard(tr + s, tc, tr + s, tc + s - 1, s); //有特殊方格后则可以继续解决该子问题
    }

    if (dr >= tr + s && dc >= tc + s) //如果特殊方格在右下区域
    {
        ChessBoard(tr + s, tc + s, dr, dc, s); //解决右下区域的子问题
    }
    else //如果特殊方格不在右下区域
    {
        Board[tr + s][tc + s] = t;                     //用L型骨牌在该区域左上角放置一个特殊方格
        ChessBoard(tr + s, tc + s, tr + s, tc + s, s); //有特殊方格后则可以继续解决该子问题
    }
}
int main()
{

    int size = 8;
    int special_row = 3;
    int special_col = 4;

    ChessBoard(0, 0, special_row, special_col, size);

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            printf("%2d ", Board[i][j]);
        }
        printf("\n");
    }
    return 0;
}

1.6 归并排序

递归的解法：

  • 先对nums[l:m]进行排序，再对nums[m+1:r]进行排序。
  • 将排好序的两部分合并，合并的时候先创建一个临时tmp，然后依次比较两部分的数值大小，将较小的放入tmp，然后移动指针；如果某一部分的元素已经全部放入，将另一部分剩余元素直接放入即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/* 
P22
2.7 合并排序
*/
# include <cstdio>
# include <vector>
using namespace std;

void merge(vector<int> &nums, int l, int m, int r)
{

    vector<int> tmp(r - l + 1);  //一定要初始化
    // vector<int> tmp;          // segmentation fault

    int i = l, j = m + 1;
    int cnt = 0;
    while(i <= m && j <= r) {
        if (nums[i] <= nums[j]) {
            tmp[cnt++] = nums[i++];
        } else {
            tmp[cnt++] = nums[j++];
        }
    }
    // j已经全部放入，i还有剩余元素
    while(i <= m) {     
        tmp[cnt++] = nums[i++];
    }
    // i已经全部放入，i还有剩余元素
    while(j <= r) {
        tmp[cnt++] = nums[j++];
    }

    //将[l:r]放回原数组
    for (int i = 0; i < r - l + 1; i++) {
        nums[i + l] = tmp[i];
    }
}
void mergeSort(vector<int> &nums, int l, int r)
{
    if (l >= r)
        return;
    int m = (l + r) / 2;
    mergeSort(nums, l, m);      // 对nums中的l到m进行排序
    mergeSort(nums, m + 1, r);  // 对nums中的m+1到r进行排序
    merge(nums, l, m, r);          // [l:m]和[m+1:r]已经排好序，将他们进行合并
}

int main(){
    vector<int> a{2, 4, 6, 2, 3, 5, 8};
    mergeSort(a, 0, (int)a.size() - 1);
    for (auto i:a){
        printf("%d ", i);
    }
    return 0;
}

整数因子分解问题

image-20220323164805370

1
2
3
4
5
6
1: 1
2: 2
3: 3
4: 4 2*2
5: 5
6: 6 2*3 3*2

（1）解法一：递归

思路：

  • 当n=1时，只有一种分解方式。
  • 当n>1时，solve(n)可以对n的每一个因子再去求该分解子问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;

int result = 0;

void solve(int n)
{
    if (n == 1)
    {
        result++;
    }
    else {
        for (int i = 2; i <= n; i++) {
            if (n % i == 0) {
                solve(n/i);
            }
        }
    }
}

int main()
{
    solve(12);
    cout << result << endl;
    return 0;
}

（2）解法二：动态规划

2 数据结构

3 动态规划

3.1 矩阵连乘问题

image-20220407102052704

（1）最优子结构

将$A_i A_{i+1} \dots A_j$的矩阵连乘定义为$A[i:j]$，那么现假设在位置$k$ 加括号使$A[i:j]=A[i:k]A[k+1:j]$，那么总计算量就等于$A[i:k]$的计算量加上$A[k+1:j]$的计算量，再加上这矩阵相乘的计算量$p_{i-1}p_k p_j$。

并且，计算$A[i:j]$的最优次序所包含的计算矩阵子链$A[1:k]$和$A[k+1:j]$的次序也是最优的，即具有最优子结构性质。

反证：如果$k$不是最优的，即存在一个更好的划分位置$k’$使$A[1:k’]$或$A[k’+1:j]$的计算量更少，那么得到的$A[1:n]$计算量也会比最优次序的计算量更少，导致矛盾。

（2）建立递归关系

用$m[i][j]$存储$A[i][j]$的最优次序计算量，则原问题的最优值为$m[1][m]$。

  • 当$i=j$时，只有一个矩阵，因此$m[i][j]=0$
  • 当$i<j$时，假设在$k$断开，则$m[i][j]=m[i][k]+m[k+1][j]+p_{i-1} p_k p_j$，由于$k$的位置不确定，因此这里需要取$min$。

递归式如下：
$$
m[i][j]= \begin{cases}0 & i=j \ \min {i \leqslant k<j}\left{m[i][k]+m[k+1][j]+p{i-1} p_{k} p_{j}\right} & i<j\end{cases}
$$
除此之外，还可以顶一个$s[i][j]$用来存储最优断开位置$k$，在计算出最优值$m[i][j]$后，可递归地由$s[i][j]$构造出相应的最优解。

（3）构造最优解

s[i][j]记录了A[i:j]最佳断开的位置k，因此当求解A[1:n]的最优加括号方式，只需要递归得查找A[i:k]和A[k+1][j]得最优加括号方式，即A[1:s[1][n]]和A[s[1][n]+1:n]。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 矩阵连乘
#include <iostream>
#include <vector>
using namespace std;

// p0p1  p2p3 p4p5  p6p7 p8p9
//  A1    A2   A3    A4   A5
// n表示矩阵个数
void MatrixChain(vector<int> &p, int n, vector<vector<int>> &m, vector<vector<int>> &s)
{
    for (int i = 0; i < n; i++)
    {
        m[i][i] = 0;
    }
    for (int r = 2; r <= n; r++)
    { // 矩阵链的个数,从2个矩阵开始
        for (int i = 1; i <= n - r + 1; i++)
        {
            int j = i + r - 1; //
            //遍历断开的位置k,找到最优次序(计算量最小)
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; //先假设在矩阵i后段断开
            s[i][j] = i;
            //从i+1出遍历断开位置k，找到最优次序
            for (int k = i + 1; k < j; k++)
            {
                int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (t < m[i][j])
                {
                    m[i][j] = i;
                    s[i][j] = k;
                }
            }
        }
    }
}

//构造最优解
void Traceback(int i, int j, vector<vector<int>> &s)
{
    if (i == j)
        return;
    Traceback(i, s[i][j], s);
    Traceback(s[i][j] + 1, j, s);
    cout << "Multiply A " << i << ", " << s[i][j];
    cout << " and A" << s[i][j] + 1 << ", " << j << endl;
}

int main()
{

    vector<int> p{30, 35, 35, 15, 15, 5, 5, 10, 10, 20, 20, 25};
    vector<vector<int>> m(12, vector<int>(12, 0));
    vector<vector<int>> s(12, vector<int>(12, 0));

    MatrixChain(p, 6, m, s);
    Traceback(1, 6, s);
    return 0;
}

3.2 最长公共子序列

image-20220407140718590

（1）最优子结构

设序列$X_m={x_1,x_2,\dots,x_m}$和$Y_n={y_1,y_2,\dots,y_n}$的最长公共子序列为$Z_k={z_1,z_2,\dots,z_k}$，可以从后往前看：

  • 如果$x_m=y_n$，那么这个数一定在公共子序列中，即$z_k=x_m=y_n$，那么原问题的规模下降为求解$X_{m-1}$和$Y_{n-1}$的最长公共子序列$Z_{k-1}$
  • 如果$x_m \neq y_n$且$z_k \neq x_m$，那么$x_m$一定不在公共子序列中，因此原问题规模可以下降为求解$X_{m-1}$和$Y_n$的最长公共子序列$Z_k$
  • 如果$x_m \neq y_n$且$z_k \neq y_n$，那么$y_n$一定不在公共子序列中，因此原问题规模可以下降为求解$Y_{n-1}$和$X_m$的最长公共子序列$Z_k$

反证：

  • 如果$z_k \neq x_m$，那么也就说明$z_k$后面还有一个公共数，即${z_1,z_2,\dots,z_k,x_m}$，那么此时公共子序列的长度为$k+1$，与$Z_k$是$X$和$Y$的最长公共子序列矛盾，因此必有$z_k=x_m=y_n$。同样的，如果$X_{m-1}$和$Y_{n-1}$有长度大于$k-1$的公共子序列$W$，那么将$x_m=y_n$加在该序列末尾，会导致$X_m$和$Y_n$的最长公共子序列长度大于$k$，矛盾。因此，$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的最长公共子序列。
  • 因为$z_k \neq x_m$，$Z_k$是$X_{m-1}$和$Y$的公共子序列，若$X_{m-1}$和$Y$有长度大于$k$的公共子序列$W$，则$W$应该也是$X_m$和$Y_n$的公共子序列，与$Z_k$是$X_m$和$Y_n$最长公共子序列矛盾。

因此，最长公共子序列问题包含了两个序列前缀的最长公共子序列的子问题，且具有最优子结构的性质。

（2）构造递归方程

  • 如果$x_m=y_n$，那么这个数一定在公共子序列中，此时只需要找到$X_{m-1}$和$Y_{m-1}$的最长公共子序列，再在其末尾加上$x_m(x_m=y_n)$即可。
  • 如果$x_m \neq y_n$，那么就需要在$X_{m-1}$和$Y_n$以及$X_m$和$Y_{n-1}$两个最长公共子序列子问题中，找出更大的那个序列。

递归方程如下，$c[i][j]$表示$X_i$与$Y_j$的最长公共子序列长度：
$$
c[i][j]= \begin{cases}
0 & i>0 ; j=0 \
c[i-1][j-1]+1 & i, j>0 ; x_{i}=y_{i} \
\max {c[i][j-1], c[i-1][j]} & i, j>0 ; x_{i} \neq y_{i}\end{cases}
$$
（3）最优解

如果除了LCS的长度，还想获取具体的LCS序列，则还需要一个$b[i][j]$用来记录当前采取了那种子问题，从而在构造LCS的时候，可以递归地进行打印。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//  最长公共子序列
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 计算最优值
void LCSLength(int m, int n, string x, string y, vector<vector<int>> &c, vector<vector<int>> &b)
{
    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            // 如果x和y中有一个序列长度为0, 则LCS长度为0
            if (i == 0 || j == 0)
            {
                c[i][j] = 0;
            }
            else if (x[i - 1] == y[j - 1])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 1;
            }
            else if (c[i - 1][j] > c[i][j - 1])
            {
                c[i][j] = c[i - 1][j];
                b[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i][j - 1];
                b[i][j] = 3;
            }
        }
    }
}

// 构造最优解
void LCS(int i, int j, string x, vector<vector<int>> &b)
{
    if (i == 0 || j == 0)
        return;
    if (b[i][j] == 1)
    {
        LCS(i - 1, j - 1, x, b);
        cout << x[i - 1];
    }
    else if (b[i][j] == 2)
    {
        LCS(i - 1, j, x, b);
    }
    else
    {
        LCS(i, j - 1, x, b);
    }
}

int main()
{
    // string x = "programming";
    // string y = "contest";
    string x = "abcfbc";
    string y = "abfcab";
    int m = x.size();
    int n = y.size();

    vector<vector<int>> c(m + 1, vector<int>(n + 1, -1));
    vector<vector<int>> b(m + 1, vector<int>(n + 1, -1));

    LCSLength(m, n, x, y, c, b);
    cout << c[m][n] << endl;
    LCS(m, n, x, b);
    return 0;
}

3.3 最大字段和

image-20220410104055295

（1）分治法：

  • 将原问题$a[1:n]$的最大子段和分解为$a[1:n/2]$和$a[n/2+1,n]$的两个子问题，分别求这两个子问题的最大子段和。

  • 在这两个子问题进行合并的时候，会存在以下三种情况：

    • $a[1:n]$的最大子段和与子问题$a[1:n/2]$的最大子段和相同。
    • $a[1:n]$的最大子段和与子问题$a[n/2+1:n]$的最大子段和相同。
    • $a[1:n]$的最大子段和$\sum_{k=i}^j{a_k}$的开始位置$i<n/2$，结束位置$j>n/2+1$。

  • 对于前两种情况，直接递归求解即可。对于第三种情况，$a[n/2]$和$a[n/2+1]$肯定在最优子段中，那么只需从位置$n/2$分别向前、向后找到最大的子段，也就是
    $$
    最大子段和=\max_{1 \leq i \leq n/2} \sum_{k=i}^{n/2}a[k] + \max_{n/2+1 \leq i \leq n} \sum_{k=n/2+1}^{j}a[k]
    $$

  • 复杂度分析：子问题规模为$n/2$,合并需要$O(n)$，递归式如下，解得$T(n)=O(n\log{n})$
    $$
    T(n) =
    \begin{cases}
    O(1) & n \leq c \
    2T(n/2) + O(n) & n \gt c

    \end{cases}
    $$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// 最大子段和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 分治法
int MaxSubSum(vector<int> &a, int left, int right)
{
    int sum = 0;
    // 当所有整数为负整数时定义最大子段和为0
    if (left == right)
    {
        sum = a[left] > 0 ? a[left] : 0;
    }
    else
    {
        int mid = (left + right) / 2;
        int leftSubSum = MaxSubSum(a, left, mid);
        int rightSubSum = MaxSubSum(a, mid + 1, right);

        //在左边找到最大的子段
        int s1 = 0;
        int leftSum = 0;
        for (int i = mid; i >= left; i--)
        {
            leftSum += a[i];
        }
        if (leftSum > s1)
        {
            s1 = leftSum;
        }
        //在左边找到最大的子段
        int s2 = 0;
        int rightSum = 0;
        for (int i = mid + 1; i <= right; i++)
        {
            rightSum += a[i];
        }
        if (rightSum > s2)
        {
            s1 = rightSum;
        }

        sum = leftSum + rightSum;
        if (sum < leftSum)
        {
            sum = leftSum;
        }
        if (sum < rightSum)
        {
            sum = rightSum;
        }
    }
    return sum;
}

int maxSum(int n, vector<int> &a)
{
    // a[1:n]的最大子段和
    return MaxSubSum(a, 1, n);
}


int main()
{
    int res;
    vector<int> a{-2, 11, -4, 13, -5, -2};

    res = maxSum(6, a);
    cout << "res:" << res << endl;
    return 0;
}

（2）动态规划

设$b[i-1]$表示$a[1:i-1]$的最大子段和，那么对于第$i$个元素$a[i]$来说，它要么合并到$a[1:i-1]$的最大子段中，要么重新成为一个新的子段，取决于$b[i-1]+a[i]$和$a[i]$的大小。

因此，动态规划的递归式如下：
$$
b[i] = \max { b[i-1] + a[i], a[i]},\space 1 \leq i \leq n
$$
该方法只需要遍历一次序列，复杂度为$O(n)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 最大子段和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSum(int n, vector<int> &a)
{
    int prev = 0, maxSum = a[0];
    for (const auto x:a)
    {
        prev = max(prev + x, x);
        maxSum = max(prev, maxSum);
    }
    return maxSum;
}

int main()
{
    int res;
    vector<int> a{-2, 11, -4, 13, -5, -2};

    res = maxSum(6, a);
    cout << "res:" << res << endl;
    return 0;
}

动态规划的遍历方式通常是以序列的结束节点为基准，如下：

image-20220410111715319

3.4 凸多边形最优三角剖分

3.5 多边形优秀

3.6 图像压缩

3.7 电路布线

3.8 流水作业调度

3.9 0-1背包问题

3.10 最优二叉搜索树