用C++的动态规划算法求解最长公共子序列问题,写出算法函数和主函数
时间: 2024-02-23 07:00:07 浏览: 23
好的,以下是C++的动态规划算法求解最长公共子序列问题的算法函数和主函数:
```C++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
int dp[MAXN][MAXN]; // dp[i][j] 表示A串前i个字符和B串前j个字符的LCS长度
char A[MAXN], B[MAXN];
int LCS(int n, int m) { // n为A串长度,m为B串长度
memset(dp, 0, sizeof(dp)); // 初始化dp数组为0
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(A[i-1] == B[j-1]) { // 找到一个相同的字符
dp[i][j] = dp[i-1][j-1] + 1; // LCS长度加1
}
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // 取左边和上边的较大值
}
}
}
return dp[n][m]; // 返回A串和B串的LCS长度
}
int main() {
cin >> A >> B;
int n = strlen(A), m = strlen(B);
cout << LCS(n, m) << endl;
return 0;
}
```
其中,`dp[i][j]`表示A串前i个字符和B串前j个字符的LCS长度,当A串第i个字符和B串第j个字符相同时,`dp[i][j]`的值为`dp[i-1][j-1] + 1`,即左上角的值加1;当A串第i个字符和B串第j个字符不同时,`dp[i][j]`的值为`max(dp[i-1][j], dp[i][j-1])`,即上方和左方的值中的较大值。
在主函数中,输入A串和B串,求出它们的LCS长度并输出。