经典演算法题每日演练——第四题最长公共子序列

一：作用
最长公共子序列的问题常用于解决字串的相似度，是一个非常实用的演算法，作为码农，此演算法是我们的必备基本功。
二：概念
举个例子，cnblogs 这个字串中子序列有多少个呢？很显然有 27 个，比如其中的 cb,cgs 等等都是其子序列，我们可以看出
子序列不见得一定是连续的，连续的那是子串。
我想大家已经了解了子序列的概念，那现在可以延伸到两个字串了，那么大家能够看出：cnblogs 和 belong 的公共子序列吗？
在你找出的公共子序列中，你能找出最长的公共子序列吗？

从图中我们看到了最长公共子序列为 blog，仔细想想我们可以发现其实最长公共子序列的个数不是唯一的，可能会有两个以上，
但是长度一定是唯一的，比如这里的最长公共子序列的长度为 4 。

三：站群解决方案
<1> 列举法
这种方法是最简单，也是最容易想到的，当然时间复杂度也是龟速的，我们可以分析一下，刚才也说过了 cnblogs 的子序列
个数有 27 个，延伸一下：一个长度为 N 的字串，其子序列有 2N 个，每个子序列要在第二个长度为 N 的字串中去匹配，匹配一次
需要 O(N) 的时间，总共也就是 O(N*2N)，可以看出，时间复杂度为指数级，恐怖的令人窒息。

<2> 动态规划
既然是经典的题目肯定是有优化空间的，并且解题方式是有固定流程的，这里我们采用的是矩阵实现，也就是二维阵列。
第一步：先计算最长公共子序列的长度。
第二步：根据长度，然后通过回溯求出最长公共子序列。
现有两个序列 X={x1,x2,x3，…xi}，Y={y1,y2,y3，….，yi}，
设一个 C[i,j]: 储存 Xi 与 Yj 的 LCS 的长度。
递推方程为：

不知道大家看懂了没？动态规划的一个重要性质特点就是解决 “子问题重叠” 的场景，可以有效的避免重复计算，根据上面的
公式其实可以发现 C[i,j] 一直储存著当前 (Xi,Yi) 的最大子序列长度。

1 using System;
2 namespace ConsoleApplication2
3 {
4 public class Program
5 {
6 static int[,] martix;
7
8 static string str1 = “cnblogs”;
9 static string str2 = “belong”;
10
11 static void Main(string[] args)
12 {
13 martix = new int[str1.Length + 1, str2.Length + 1];
14
15 LCS(str1, str2);
16
17 //只要拿出矩阵最后一个位置的数字即可
18 Console.WriteLine(“ 当前最大公共子序列的长度为:{0}”, martix[str1.Length, str2.Length]);
19
20 Console.Read();
21 }
22
23 static void LCS(string str1, string str2)
24 {
25 //初始化边界，过滤掉 0 的情况
26 for (int i = 0; i <= str1.Length; i++) 27 martix[i, 0] = 0; 28 29 for (int j = 0; j <= str2.Length; j++) 30 martix[0, j] = 0; 31 32 //填充矩阵 33 for (int i = 1; i <= str1.Length; i++) 34 { 35 for (int j = 1; j <= str2.Length; j++) 36 { 37 //相等的情况 38 if (str1[i - 1] == str2[j - 1]) 39 { 40 martix[i, j] = martix[i - 1, j - 1] + 1; 41 } 42 else 43 { 44 //比较“左边”和“上边“，根据其max来填充 45 if (martix[i - 1, j] >= martix[i, j – 1])
46 martix[i, j] = martix[i – 1, j];
47 else
48 martix[i, j] = martix[i, j – 1];
49 }
50 }
51 }
52 }
53 }
54 }

图大家可以自己画一画，程式码完全是根据上面的公式照搬过来的，长度的问题我们已经解决了，这次要解决输出最长子序列的问题，
我们采用一个标记函式 Flag[i,j]，当
①：C[i,j]=C[i-1,j-1]+1 时标记 Flag[i,j]=”left_up”; （左上方箭头）
②：C[i-1,j]>=C[i,j-1] 时标记 Flag[i,j]=”left”; （左箭头）
③: C[i-1,j]= martix[i, j – 1])
53 {
54 martix[i, j] = martix[i – 1, j];
55 flag[i, j] = “left”;
56 }
57 else
58 {
59 martix[i, j] = martix[i, j – 1];
60 flag[i, j] = “up”;
61 }
62 }
63 }
64 }
65 }
66
67 static void SubSequence(int i, int j)
68 {
69 if (i == 0 || j == 0)
70 return;
71
72 if (flag[i, j] == “left_up”)
73 {
74 Console.WriteLine(“{0}: 当前座标:（{1},{2}）”, str2[j – 1], i – 1, j – 1);
75
76 //左前方
77 SubSequence(i – 1, j – 1);
78 }
79 else
80 {
81 if (flag[i, j] == “up”)
82 {
83 SubSequence(i, j – 1);
84 }
85 else
86 {
87 SubSequence(i – 1, j);
88 }
89 }
90 }
91 }
92 }

由于直接绘图很麻烦，嘿嘿，我就用手机拍了张：

好，我们再输入两个字串：

1 static string str1 = “abcbdab”;
2
3 static string str2 = “bdcaba”;

通过上面的两张图，我们来分析下它的时间复杂度和空间复杂度。
时间复杂度：构建矩阵我们花费了 O(MN) 的时间，回溯时我们花费了 O（M+N) 的时间，两者相加最终我们花费了 O(MN) 的时间。
空间复杂度：构建矩阵我们花费了 O(MN) 的空间，标记函式也花费了 O(MN) 的空间，两者相加最终我们花费了 O(MN) 的空间。

一：作用
最长公共子序列的问题常用于解决字串的相似度，是一个非常实用的演算法，作为码农，此演算法是我们的必备基本功。
二：概念
举个例子，cnblogs 这个字串中子序列有多少个呢？很显然有 27 个，比如其中的 cb,cgs 等等都是其子序列，我们可以看出
子序列不见得一定是连续的，连续的那是子串。
我想大家已经了解了子序列的概念，那现在可以延伸到两个字串了，那么大家能够看出：cnblogs 和 belong 的公共子序列吗？
在你找出的公共子序列中，你能找出最长的公共子序列吗？