最长公共子序列 递归+迭代 C++

给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，求最长公共子序列。

要求：用递归和迭代两种方法写代码。

递归：

#include 
using namespace std;

string a, b;
int p[100][100];

int LCS(int n, int m){
    if (n == -1 || m == -1) return 0;
    if (a[n] == b[m])
        return LCS(n - 1, m - 1) + 1;
    else
        return max(LCS(n - 1, m), LCS(n, m - 1));
}
string LCSR(int n, int m){
    if (n == -1 || m == -1) return "";
    if (a[n] == b[m])
        return LCSR(n - 1, m - 1) + a[n];
    else
        return LCS(n - 1, m) > LCS(n, m - 1) ? LCSR(n - 1, m) : LCSR(n, m - 1);

}//递归

int main() {

	cin >> a >> b;

	cout << "递归:" << endl;
	cout << LCS(a.length()-1, b.length()-1) << endl;//数组从0开始
	cout << LCSR(a.length(), b.length()) << endl;//递归
    
	return 0;
}

 迭代：

//给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}求所有最长公共子序列
#include 
using namespace std;

string a, b;
int p[100][100];

int LCSS(int n, int m){
    memset(p, 0, 100);	//p设为0
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    {
        if (a[i-1] == b[j-1])
            p[i][j] = p[i - 1][j - 1] + 1;
        else p[i][j] = max(p[i - 1][j], p[i][j - 1]);
    }
    return p[n][m];
}
void LCS2(int n, int m){
    char c[100];
    int k = 0;
    memset(p, 0, 100);
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    {
        if (a[i - 1] == b[j - 1])
            p[i][j] = p[i - 1][j - 1] + 1;
        else p[i][j] = max(p[i - 1][j], p[i][j - 1]);
    }
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    {
        if (p[i][j] == p[i - 1][j] + 1 && p[i][j] == p[i][j - 1] + 1)
        {
            c[k++] = a[i - 1]; break;
        }
    }
    c[k] = '';
    cout << c << endl;
}//迭代


int main() {

	cin >> a >> b;

	cout << "迭代:" << endl;
    cout << LCSS(a.length(), b.length()) << endl;//迭代	数组从0开始
    LCS2(a.length(), b.length());
    
	return 0;
}