本文介绍 有趣的算法问题之巧思妙想

有趣的算法问题之巧思妙想

本文由在当地较为英俊的男子金天大神原创，版权所有，欢迎转载，本文首发地址 https://jinfagang.github.io 。但请保留这段版权信息，多谢合作，有任何疑问欢迎通过微信联系我交流：jintianiloveu

有趣的算法

算法之所以有趣，在于他能够化繁为简，他能概括统御世间万物，将一个复杂的问题归结为一个非常简单的问题。其实所有高阶的算法，都可以用两个大的方法去解决，而且屡试不爽。分别是动态规划和贪心算法.
我们先从一道动态规划的问题先说起吧。

动态规划问题

最长公共子序列问题(LCS)，给定两个序列X和Y，求他们之间最长的公共子序列。

哇，这题目感觉有点难啊。最长公共子序列问题其实可以归结为最最最最最简单的一个递推表达式，首先我们假设序列X元素个数为i，Y为j，C[i, j]表示最长公共子序列的长度。好那么问题就变成了，如何求取这个最长公共子序列的长度问题。公式也是非常简单 ==easy== :smile:

$$C[i, j] = \left{ \begin{array}{lr} 0,\quad if \ x=0 \, or \ y=0 \ C[i-1, j-1] + 1, \quad if \; i,j>0 \; , x_i=y_i \ max{C[i, j-1], C[i-1, j]} , \quad if \ i,j>0, \ x_i\neq x_j \end{array} \right. $$

这个公式还是非常难打啊，大概就是这么一个意思吧。咋一看这个表达式很牛逼啊，你随便给我两个序列，我通过他就可以求出最长子序列的长度？闲话不多说，让我们直接上代码看一下到底有没有这么牛逼。

假如我们有两个序列，我们用字符串来表示吧 X=cnblogs, Y=belong, 肉眼可以看到最长子序列为blog。那么长度就是4，让我们看看到底有没有这么牛逼。

在这之前，我得理清一下思路，首先是这样的，我们求取的这个C[i, j]，实际上就是一个二维的矩阵，你想啊i是从0变到i，j是从0变到j，那一路求过来，不就是一个i行j列的矩阵吗？目标值就是最右下角的这个元素。既然如此那么变成就好办了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// this code calculate the max length of common sub-sequence of 2 strings
int lcs_length(string a, string b) {
    // given 2 string, return the LCS length
    // define a 2 dim array
    int matrix[a.size()+1][b.size()+1];
    for (int i = 0; i <= a.size(); ++i) {
        matrix[i][0] = 0;
    }
    for (int j = 0; j <= b.size(); ++j) {
        matrix[0][j] = 0;
    }
    for(int i = 1; i <= a.size(); i++) {
        for(int j = 1; j <= b.size(); j++) {
            if (a[i-1] == b[j-1]) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
            } else {
                matrix[i][j] = matrix[i][j-1] > matrix[i-1][j] ? matrix[i][j-1] : matrix[i-1][j];
            }
        }
    }
    return matrix[a.size()][b.size()];
}

很显然，这个函数可以正确的得到最长公共子串的长度。看上去还是很牛逼，但是其实道理也非常简单，无外乎就是上面的三个公式。那么你可能回问了，上面三个公式是怎么来的呢？其实就是一个非常简单的递推，假如说公共子串Z的最后一个元素是X的最后一个元素，那么肯定也是Y的最后元素，那如果将X去掉最后元素，Y去掉最后一个元素，最长公共子串就是去掉之后的+1，就是加去掉的这个嘛。那如果说最后一个元素都不是X， Y的最后元素，那更好办了，这个时候公共子串就是X和Y的中间某一个子串嘛，这个时候X去掉最后一个，再来求公共子串，还是一样啊，或者Y去掉一个，也是一样啊，就直接就等于X或者Y去掉一个的共同子串的最大值了。(有人会问，为什么不等于X，Y都去掉一个的最大值呢？也就是 $$ max{C[i-1, j-1], C[i-1, j-1]}$$， 这是不行的，原因很简单，你X去掉一个之后，最长子串就有可能包含Y的最后一个值了，你都去掉会减少很多种情况，不可取 )。

这个问题我们已经完成了历史性的一步： 可以求取两个序列的最长子序列的长度。， 那么下一步就是，怎么找到这个最长子序列。这一步思路是这样的：

(你可能无法想象，我完成求最大公共子序列上调试C++代码踩了一下午坑，我曹，真的是天坑)。先说一下思路吧，非常复杂，首先在上面的函数里面我们给他传入一个pFlag的二维数组，注意这是一个指针，因为后面需要递归遍历他。在这个二维数组里面存储的大小和matrix是一样，只不过这里面存储的都是字符串，为了便于理解我存储为 : “left”, “up”, “left_up”，三种字符串，其实你如果自己画了matrix这个表，就会发现，其实可以通过这样的箭头去回溯这个最长子序列是什么，你会发现恰恰是箭头所指向的路径。然后我们用一个函数递归，根据箭头来找到对应的子序列。所有代码如下：

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
#include <iostream>
#include <vector>
using namespace std;
void sub_sequence(int i, int j, string **pFlag, string a) {
    if (i == 0 || j == 0) {
        return;
    }
    if (pFlag[i][j] == "left_up") {
        sub_sequence(i - 1, j - 1, pFlag, a);
        cout << a[i-1] << " ";
    } else {
        if (pFlag[i][j] == "left") {
            sub_sequence(i, j-1, pFlag, a);
        } else {
            sub_sequence(i-1, j, pFlag, a);
        }
    }
}
int lcs_length(string a, string b, string **pFlag) {
    // given 2 string, return the LCS length
    // define a 2 dim array
    int matrix[a.size()+1][b.size()+1];
    for (int i = 0; i <= a.size(); ++i) {
        matrix[i][0] = 0;
    }
    for (int j = 0; j <= b.size(); ++j) {
        matrix[0][j] = 0;
    }
    for(int i = 1; i <= a.size(); i++) {
        for(int j = 1; j <= b.size(); j++) {
            if (a[i-1] == b[j-1]) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
                // using string to indicate location
                pFlag[i][j] = "left_up";
            } else {
                if (matrix[i][j-1] > matrix[i-1][j]) {
                    matrix[i][j] = matrix[i][j-1];
                    pFlag[i][j] = "left";
                } else {
                    matrix[i][j] = matrix[i-1][j];
                    pFlag[i][j] = "up";
                }
            }
        }
    }
    return matrix[a.size()][b.size()];
}
int main()
{
    string b = "gheteuponthiop";
    string a = "giothuphyo";
    // 这里应该是**pFlag, markdown渲染有问题，二维指针
    auto ** pFlag = new string* [a.size() + 1];
    for (int k = 0; k <= a.size(); ++k) {
        pFlag[k] = new string[b.size() + 1];
    }
    int l = lcs_length(a, b, pFlag);
    sub_sequence((int) a.size(), (int) b.size(), pFlag, a);
    cout << endl;
    cout << l << endl;
    return 0;
}

收工！以后遇到求最大公共子序列问题就来我的博客！！！！

写到这里发现并不是那么有趣了。很复杂啊。。。不过坚信那句，万变不离其宗。