最长公共子序列问题，经典dp

#include #include #include using namespace std;char a[2000], b[2000];int al, bl, m;int dp[2000][2000];int main() {	while (cin >> a >> b) {		al = strlen(a);		bl = strlen(b);		bool one = false;		for (int i = 0; i < al; ++i) {			if (a[i] == b[0]) {				dp[i][0] = 1;				one = true;			} else {				dp[i][0] = one ? 1 : 0;			}		}		one = false;		for (int i = 0; i < bl; ++i) {			if (a[0] == b[i]) {				dp[0][i] = 1;				one = true;			} else {				dp[0][i] = one ? 1 : 0;			}		}		m = 0;		for (int i = 1; i < al; ++i) {			for (int j = 1; j < bl; ++j) {				if (a[i] == b[j])					dp[i][j] = dp[i - 1][j - 1] + 1;				else					dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];				if (dp[i][j] > m)					m = dp[i][j];			}		}		cout << m << endl;	}	return 0;}