两个串a1 a2 a3···an b1 b2 b3···bm
这俩的最长公共子序列为c1 c2 c3···ck
dp[i][j]表示串a长度为i时和串b长度为j时的最长公共子序列的长度
1、若an == bn，则ck = an，即c1 c2 c3···c(k-1)为a1 a2 a3···a(n-1) 和 b1 b2 b3···b(m-1)的最长公共子序列，同理第i，j个位置，dp[i][j] = dp[i - 1][j - 1] + 1;
2、若an != bn ，若ck != an, 即c1 c2 c3···c(k-1)为a1 a2 a3···a(n-1) 和 b1 b2 b3···b(m)的最长公共子序列，同理第i，j个位置，dp[i][j] = dp[i - 1][j];
3、若an != bn ，若ck != bm, 即c1 c2 c3···c(k-1)为a1 a2 a3···an 和 b1 b2 b3···b(m - 1)的最长公共子序列，同理第i，j个位置，dp[i][j] = dp[i][j - 1];
综上
if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
模板题HDU - 1159
int dp[1010][1010]; int main() { string str1, str2; while(cin >> str1 >> str2) { mem(dp, 0); int len1 = str1.size(); int len2 = str2.size(); for(int i = 0; i < len1; i++) for(int j = 0; j < len2; j++) if(str1[i] == str2[j]) dp[i + 1][j + 1] = dp[i][j] + 1; else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); cout << dp[len1][len2] << endl; } return 0; }
原文：https://www.cnblogs.com/WTSRUVF/p/14266965.html