要求：

掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长子序列

算法解析：

令dp[i][j]表示字符串A的i号位和字符串B的j号位之前的LCS长度，可以根据两个字符串的情况分为两种策略
1、 若A[i]=B[j]，则字符串A与字符串B的LCS增加1位，即有dp[i][j]=dp[i-1][j-1]+1
2、 若A[i]!=B[j],则LCS无法延长，因此dp[i][j]=max(dp[i-1][j],dp[i][j-1])

边界：dp[0][j]=dp[i][0]=0
Tips:输入的两个字符串A、B下标是从0开始，那么就会要寻找dp[-1]的情况，这是需要处理的

• 让数组A、B从下标1开始读入，利用c语言的gets(A+1)可以实现，但由于该函数并不安全所以在最新的ide中已被弃用，所以可以再建两个数组来承接AB来实现下标为1，但这样会造成开销
• 让转移矩阵变形，dp[i+1][j+1]=dp[i][j]+1,相当于把原来的元素全部向前移一个单位，这样dp[0][]就可以表现为A[0]之前的LCS长度

代码：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string A, B;
int dp[12][12];
int C[100][100];
stack<char> same;
int main() {
    int n;
    cin >> A;
    cin >> B;
    for (int i = 0; i <= A.length(); i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= B.length(); j++) {
        dp[0][j] = 0;
    }
    for (int i = 0; i < A.length(); i++) {
        for (int j = 0; j < B.length(); j++) {
            if (A[i] == B[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                C[i + 1][j + 1] = 1;
            }
            else if(dp[i][j+1]>=dp[i+1][j]){
                dp[i + 1][j + 1] = dp[i][j + 1];
                C[i + 1][j + 1] = 2;
            }
            else {
                dp[i + 1][j + 1] = dp[i+1][j];
                C[i + 1][j + 1] = 3;
            }
        }
    }
    for (int i = A.length(), j = B.length(); i >= 0 && j >= 0;) {
        if (C[i][j] == 1) {
            i--;
            j--;
            same.push(A[i]);
        }
        else if (C[i][j] == 2) {
            i--;
        }
        else {
            j--;
        }
    }
    cout << dp[A.length()][B.length()] << endl;
    while(!same.empty()){
        cout << same.top();
        same.pop();
    }
    return 0;
}

样例：

输出.png

如有错误，欢迎斧正