LCS的理解

  1. 1.暴力求解
  2. 2.DP

1.暴力求解

2.DP

dp[i][j]为a串第i位置b串第j位置以前两个序列最大的lcs

那么也就有dp[0][0] = 0; dp[a.len()][b.len]为所求

状态转移方程:

if a[i] == b[j] dp[i][j] = dp[i-1][j-1] + 1
if a[i] != b[j] dp[i][j] = max(dp[i-1][j],dp[i][j-1])

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dp[100][100];
string str1,str2;
int l1 = str1.length();
int l2 = str2.length();

for(int i = 1; i <= l1; i++) {
for(int j = 1; j <= l2; j++) {
if(str1[i] == str2[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
}
}
cout << dp[len1][len2];

例题:

略,日后补
script>