1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 char str1[55], str2[55]; 6 int f[55][55];//记录状态 7 //动态规划是一种记忆化搜索 8 /*有俩个字符串，求出他们的最长公共子序列 9 ，例如: 10 acdtfs 11 aldtks 12 最长公共子序列是adts,长度为4 13 n,m 14 string1(length = n) 15 string2(length = m) 16 f[i][j]表示1串第i个与第二个串第j个匹配得到 17 的子序列最大长度 18 f[i][j] = max(f[i - 1][j], f[i][j - 1]); 19 f[i - 1][j - 1] + 1; 20 */ 21 int main(){ 22 int i, j, k; 23 int n, m; 24 scanf("%d%d",&n,&m); 25 scanf("%s%s",str1 + 1, str2 + 1); 26 f[0][0] = 0; 27 for(int i = 1; i <= n; i++){ 28 for(int j = 1; j <= m; j++){ 29 if(str1[i] == str2[j]){ 30 f[i][j] = f[i - 1][j - 1] + 1; 31 } 32 f[i][j]=max(f[i][j], f[i-1][j]); 33 f[i][j]=max(f[i][j], f[i][j-1]); 34 } 35 } 36 printf("%d ", f[n][m]); 37 return 0; 38 }
1 #include <iostream> 2 using namespace std; 3 /*有一串数，求出它的最大不下降子序列的 4 长度(等于也包括) 5 如1, 2, 5, 3, 6, 2, 9, 10 6 答案是 7 1 2 3 6 9 10(这只是其中之一) 8 f[i]表示子序列包括数字i的时候，最长不下降子序列的长度 9 f[i] = max(f[j] + 1) a[i] > a[j]; 10 ans = max(f[i]) 11 */ 12 int a[222]; 13 int f[222]; 14 int memory[222];//记录状态 15 int main(){ 16 int i, j, k; 17 int n; 18 scanf("%d", &n);//数串的长度 19 for(i = 1; i <= n; i++){ 20 scanf("%d", &a[i]); 21 } 22 int temp; 23 f[1] = 1;//第一个为1 24 for(i = 2; i <= n; i++){ 25 f[i] = 0; 26 for(j = 1; j <= i - 1; j++){ 27 if(a[i] > a[j]){//如果后面的数字更大 28 if(f[i] < f[j] + 1){//如果后面数字的最长子序列长度小于前面最长子序列长度 + 1 29 f[i] = f[j] + 1;//更新此时的最长子序列长度 30 memory[i] = j;//记录i位置的前一个位置 31 } 32 } 33 } 34 } 35 int ans = 0, mark;//mark用来取得记录最大不下降子序列的下标,ans用来记录大子序列的值 36 for(i = 1; i <= n; i++){ 37 if(ans < f[i]){ 38 mark = i; 39 ans = f[i]; 40 } 41 } 42 temp = mark; 43 //倒序输出记录状态 (这里可以利用一个栈顺序输出) 44 while(temp > 0){ 45 printf("%d ", a[temp]); 46 temp = memory[temp]; 47 } 48 printf(" %d ", ans); 49 return 0; 50 }
最长公共子序列的优秀博文:https://blog.csdn.net/someone_and_anyone/article/details/81044153