实验2-1

实验2-1 最长公共子序列

如题：

思路：

很明显的动态规划问题

找出递推公式，《计算机算法设计与分析第五版 王晓东》p55

建议画图理解

s1==s2

s1!=s2

然后填表

s1= a b c f b c s2= a b f c a b （第一组数据）

以a行举例

a比a一样，所以 a行a列 0+1=1 (根据公式i-1，j-1 0行0列的值+1)

a比b不一样，所以max(1,0)，填1

a比c不一样，填1

a比f不一样，填1

a比b不一样，填1

a比c不一样，填1

怎么根据表找最大公共子串反推

答案明显不唯一，注意题目：以第一个串中字符的出现次序优先

a b c f b c为第一串：

也可以这样找

a b f c a b为第一串：

the same

代码：

#include <stdio.h>
#include <string.h>

#define MAX_LENGTH 100

//动态规划
void LCS(char t[], char s[]) {

    int m = strlen(s);
    int n = strlen(t);
    
    //二维数组dp，保存最长公共子序列的长度
    int dp[MAX_LENGTH+1][MAX_LENGTH+1];
    
    //初始化
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= m; i++) {  //比对 二维数组或者说是矩阵 里面的值 并给计算每行每列的值（使用递推公式）
        
        for (int j = 1; j <= n; j++) {
            //如果s和t的当前字符相等，则公共子序列的长度为前一个状态的长度加1
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } 
            else {
                //否则，公共子序列的长度取前一个状态中较大值
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }
    
    //最长公共子序列的长度
    printf("%d\n", dp[m][n]);
    
    //构造最长公共子序列
    char lcs[MAX_LENGTH];
    int i = m;
    int j = n;
    int index = dp[m][n]; //根据规划表，进行反推最长子序列，每找到一个字符减 1


    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            //如果当前字符相等，则将该字符添加到最长公共子序列中
            lcs[--index] = s[i - 1];
            i--;
            j--;
        } 
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            //进行位置向上移动
            i--;
        } 
        else {
            //位置向左移动
            j--;
        }
    }
    
    //输出最长公共子序列
    for (int k = 0; k < dp[m][n]; k++) {

        printf("%c", lcs[k]);
    }
}

int main() {

    int T;
    scanf("%d", &T);
    
    for (int i = 0; i < T; i++) {

        char s[MAX_LENGTH], t[MAX_LENGTH];
        scanf("%99s%99s", s, t);
        LCS(s, t);
        if(i < (T-1)){
            printf("\n");
        }
          
    }

    return 0;
}

还是太菜了

PTA一直显示答案错误

不！冷静分析一番，应该是输出的问题，题目暗示用字符串，但是c语言没有string类

改成C++

#include<iostream>
#include<string>
#include<algorithm> 

#define MAX_LENGTH 1000

//动态规划
void LCS(std::string t, std::string s) {
    int m = s.length();
    int n = t.length();

    //二维数组dp，保存最长公共子序列的长度
    int dp[MAX_LENGTH + 1][MAX_LENGTH + 1];

// 初始化
for (int i = 0; i <= m; i++) {
    std::fill(dp[i], dp[i] + n + 1, 0);
}

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            //如果s和t的当前字符相等，则公共子序列的长度为前一个状态的长度加1
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                //否则，公共子序列的长度取前一个状态中较大值
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    //最长公共子序列的长度
    std::cout << dp[m][n] << std::endl;

    //构造最长公共子序列
    char lcs[MAX_LENGTH];
    int i = m;
    int j = n;
    int index = dp[m][n];

    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            //如果当前字符相等，则将该字符添加到最长公共子序列中
            lcs[--index] = s[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            //进行位置向上移动
            i--;
        } else {
            //位置向左移动
            j--;
        }
    }

    //输出最长公共子序列
    for (int k = 0; k < dp[m][n]; k++) {
        std::cout << lcs[k];
    }
}

int main() {
    int T;
    std::cin >> T;

    for (int i = 0; i < T; i++) {
        std::string s, t;
        std::cin >> s >> t;
        LCS(s, t);
        if (i < (T - 1)) {
            std::cout << std::endl;
        }
    }

    return 0;
}