AcWing 897. 最长公共子序列
原题链接
简单
作者:
NinjaNB
,
2024-03-14 19:51:19
,
所有人可见
,
阅读 16
暴力递归+记忆化搜索
#include <iostream>
using namespace std;
int dp[1000][1000];
int n, m;
//返回值代表以i结尾和以j结尾的最大公共子序列长度
int FindCommon(string str1, string str2,int i,int j) {
if (i < 0 || j < 0)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
int a = FindCommon(str1, str2, i - 1, j - 1);
int b = FindCommon(str1, str2, i - 1, j);
int c = FindCommon(str1, str2, i, j - 1);
int d = str1[i] == str2[j] ? a + 1 : 0;
dp[i][j] = max(max(a, b), max(c, d));
return dp[i][j];
}
int main() {
cin >> n >> m;
string str1, str2;
cin >> str1 >> str2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = -1;
}
}
cout << FindCommon(str1, str2,str1.length() - 1,str2.length() - 1) << endl;
return 0;
}