序列型动态规划（动态规划基础篇之最长公共子序列问题）

序列型动态规划（动态规划基础篇之最长公共子序列问题）对序列 1 3 5 4 2 6 8 7和序列 1 4 8 6 7 5 来说例如：对于一个长度为n的序列，它一共有2^n 个子序列，有(2^n – 1)个非空子序列。请注意：子序列不是子集，它和原始序列的元素顺序是相关的。（2）公共子序列 ： 顾名思义，如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。

一些概念：

（1）子序列： 一个序列A ＝ a1 a2 ……an 中任意删除若干项，剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。

例如：

对序列 1 3 5 4 2 6 8 7来说，序列3 4 8 7 是它的一个子序列。

对于一个长度为n的序列，它一共有2^n 个子序列，有(2^n – 1)个非空子序列。

请注意：子序列不是子集，它和原始序列的元素顺序是相关的。

（2）公共子序列 ： 顾名思义，如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。

例如：

对序列 1 3 5 4 2 6 8 7和序列 1 4 8 6 7 5 来说

序列1 8 7是它们的一个公共子序列。

请注意： 空序列是任何两个序列的公共子序列。

例如： 序列1 2 3和序列4 5 6的公共子序列只有空序列。

（3）最长公共子序列

A和B的公共子序列中长度最长的（包含元素最多的）叫做A和B的公共子序列。

另外，说一下复杂度？

时间复杂度时O(n * m)，空间也是O(n * m)

今天对LCS的讲解就到这里，聪明的你是不是已经蠢蠢欲动要AC问题啦？ 心动不如行动，赶快吧。

在这里，本宝宝找到了两个模板，先收藏着，等过段在细细琢磨琢磨，有新的收获再补充。

代码一是让你输入两个序列，然后输出最长公共子序列和长度。

代码二是让你输入三个序列，然后输出最长公共子序列的长度。

代码一：

1. 
   
2. #include <stdio.h>
3. #include <string.h>
4. #include <stdlib.h>
5. int LCSLength(char* str1 char* str2 int **b)
6. {
7. int i j length1 length2 len;
8. length1 = strlen(str1);
9. length2 = strlen(str2);
11. //双指针的方法申请动态二维数组
12. int **c = new int*[length1 1]; //共有length1 1行
13. for(i = 0; i < length1 1; i )
14. c[i] = new int[length2 1];//共有length2 1列
16. for(i = 0; i < length1 1; i )
17. c[i][0]=0; //第0列都初始化为0
18. for(j = 0; j < length2 1; j )
19. c[0][j]=0; //第0行都初始化为0
21. for(i = 1; i < length1 1; i )
22. {
23. for(j = 1; j < length2 1; j )
24. {
25. if(str1[i-1]==str2[j-1])//由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-1个元素
26. {
27. c[i][j]=c[i-1][j-1] 1;
28. b[i][j]=0; //输出公共子串时的搜索方向
29. }
30. else if(c[i-1][j]>c[i][j-1])
31. {
32. c[i][j]=c[i-1][j];
33. b[i][j]=1;
34. }
35. else
36. {
37. c[i][j]=c[i][j-1];
38. b[i][j]=-1;
39. }
40. }
41. }
42. /*
43. for(i= 0; i < length1 1; i )
44. {
45. for(j = 0; j < length2 1; j )
46. printf("%d " c[i][j]);
47. printf("\n");
48. }
49. */
50. len=c[length1][length2];
51. for(i = 0; i < length1 1; i ) //释放动态申请的二维数组
52. delete[] c[i];
53. delete[] c;
54. return len;
55. }
56. void PrintLCS(int **b char *str1 int i int j)
57. {
58. if(i==0 || j==0)
59. return ;
60. if(b[i][j]==0)
61. {
62. PrintLCS(b str1 i-1 j-1);//从后面开始递归，所以要先递归到子串的前面，然后从前往后开始输出子串
63. printf("%c" str1[i-1]);//c[][]的第i行元素对应str1的第i-1个元素
64. }
65. else if(b[i][j]==1)
66. PrintLCS(b str1 i-1 j);
67. else
68. PrintLCS(b str1 i j-1);
69. }
71. int main(void)
72. {
73. char str1[100] str2[100];
74. int i length1 length2 len;
75. printf("请输入第一个字符串：");
76. gets(str1);
77. printf("请输入第二个字符串：");
78. gets(str2);
79. length1 = strlen(str1);
80. length2 = strlen(str2);
81. //双指针的方法申请动态二维数组
82. int **b = new int*[length1 1];
83. for(i= 0; i < length1 1; i )
84. b[i] = new int[length2 1];
85. len=LCSLength(str1 str2 b);
86. printf("最长公共子序列的长度为：%d\n" len);
87. printf("最长公共子序列为：");
88. PrintLCS(b str1 length1 length2);
89. printf("\n");
90. for(i = 0; i < length1 1; i )//释放动态申请的二维数组
91. delete[] b[i];
92. delete[] b;
93. system("pause");
94. return 0;
95. }

代码二：

1. 
   
2. #include <stdio.h>
3. #include <string.h>
4. #include <stdlib.h>
5. int max1(int m int n)
6. {
7. if(m>n)
8. return m;
9. else
10. return n;
11. }
12. int max2(int x int y int z int k int m int n)
13. {
14. int max=-1;
15. if(x>max)
16. max=x;
17. if(y>max)
18. max=y;
19. if(z>max)
20. max=z;
21. if(k>max)
22. max=k;
23. if(m>max)
24. max=m;
25. if(n>max)
26. max=n;
27. return max;
28. }
29. int LCSLength(char* str1 char* str2 char* str3) //求得三个字符串的最大公共子序列长度并输出公共子序列
30. {
31. int i j k length1 length2 length3 len;
32. length1 = strlen(str1);
33. length2 = strlen(str2);
34. length3 = strlen(str3);
36. //申请动态三维数组
37. int ***c = new int**[length1 1]; //共有length1 1行
38. for(i = 0; i < length1 1; i )
39. {
40. c[i] = new int*[length2 1]; //共有length2 1列
41. for(j = 0; j<length2 1; j )
42. c[i][j] = new int[length3 1];
43. }
45. for(i = 0; i < length1 1; i )
46. {
47. for(j = 0; j < length2 1; j )
48. c[i][j][0]=0;
49. }
50. for(i = 0; i < length2 1; i )
51. {
52. for(j = 0; j < length3 1; j )
53. c[0][i][j]=0;
54. }
55. for(i = 0; i < length1 1; i )
56. {
57. for(j = 0; j < length3 1; j )
58. c[i][0][j]=0;
59. }
61. for(i = 1; i < length1 1; i )
62. {
63. for(j = 1; j < length2 1; j )
64. {
65. for(k = 1; k < length3 1; k )
66. {
67. if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1])
68. c[i][j][k]=c[i-1][j-1][k-1] 1;
69. else if(str1[i-1]==str2[j-1] && str1[i-1]!=str3[k-1])
70. c[i][j][k]=max1(c[i][j][k-1] c[i-1][j-1][k]);
71. else if(str1[i-1]==str3[k-1] && str1[i-1]!=str2[j-1])
72. c[i][j][k]=max1(c[i][j-1][k] c[i-1][j][k-1]);
73. else if(str2[j-1]==str3[k-1] && str1[i-1]!=str2[j-1])
74. c[i][j][k]=max1(c[i-1][j][k] c[i][j-1][k-1]);
75. else
76. {
77. c[i][j][k]=max2(c[i-1][j][k] c[i][j-1][k] c[i][j][k-1] c[i-1][j-1][k] c[i-1][j][k-1] c[i][j-1][k-1]);
78. }
79. }
80. }
81. }
82. len=c[length1][length2][length3];
83. for(i = 1; i < length1 1; i ) //释放动态申请的三维数组
84. {
85. for(j = 1; j < length2 1; j )
86. delete[] c[i][j];
87. delete[] c[i];
88. }
89. delete[] c;
90. return len;
91. }
93. int main(void)
94. {
95. char str1[100] str2[100] str3[100];
96. int len;
98. printf("请输入第一个字符串：");
99. gets(str1);
100. printf("请输入第二个字符串：");
101. gets(str2);
102. printf("请输入第三个字符串：");
103. gets(str3);
104. len=LCSLength(str1 str2 str3);
105. printf("最长公共子序列的长度为：%d\n" len);
106. system("pause");
107. return 0;
108. }