算法设计与分析 | 动态规划（最长公共子序列）

题目描述

?????? 需要你做的就是写一个程序，得出最长公共子序列。
?????? 最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

输入

??? 第一行给出一个整数N(0<N<100)表示待测数据组数
??? 接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000.

输出

?? 每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。

样例输入

2
asdf
adfsd
123abc
abc123abc

样例输出

3
6

分析：

该题可以通过动态规划来做，填一个i行j列的二维数组，其中i代表第一个字符串长度，j代表第二个字符串长度，根据以下公式来找最终的最长公共子序列：

代码：

#include <stdio.h>
#include <string.h>
#define N 1001
//最长公共子序列
int longzxl(char* a, char* b) {
    int asz = strlen(a);
    int bsz = strlen(b);
    int c[N+1][N+1];
    int i, j=0, count = 0;
    for (i = 0; i <= asz; i++) {
        for(j=0;j<=bsz;j++){
            if (i == 0 || j == 0) {
                c[i][j] = 0;
            }
            else if (a[i - 1] == b[j - 1]) {
                c[i][j] = 1 + c[i - 1][j - 1];
            }
            else {
                c[i][j] = c[i - 1][j] > c[i][j - 1] ? c[i - 1][j] : c[i][j - 1];
            }
        }
    }
    return c[asz][bsz];
}
void main() {
     
    int n;
    scanf("%d", &n);
    while (n--) {
        char a[N];
        char b[N];
        scanf("%s %s", a, b);
        printf("%d\n", longzxl(a, b));
    }
}

参考：动态规划解最长公共子序列(LCS)(附详细填表过程)-CSDN博客