POJ-1458.CommonSubsequence.(DP：最长公共子序列裸题)
本题大意：给出两个字符串，让你求出最长公共子序列的长度并输出。
本题思路：本题是经典的DP问题，由于是两个字符串，那么我们就用一个二维数组来进行区分，用dp[ i ][ j ]来表示在s1和s2中分别以i， j 结尾的子串中最长公共子序列的长度，很容易得出dp[i + 1] [j + 1] 的值只与dp[ i ][ j ] ，dp[i + 1][ j ] ， dp[[ i ][ j + 1]的值有关，那么我们就可以列出状态转移方程。
dp[ i + 1][j + 1] = s1[ i ] == s2[ j ] ? dp[ i ][ j ] + 1 : max(dp[i + 1][ j ], dp[ i ][j + 1]);
参考代码：
1 #include <iostream> 2 #include <string> 3 using namespace std; 4 5 const int maxn = 1e3; 6 int dp[maxn][maxn]; 7 8 int main () { 9 string s1, s2; 10 while(cin >> s1 >> s2) { 11 dp[0][0] = 0; 12 int n = s1.length(), m = s2.length(); 13 for(int i = 0; i < n; i ++) { 14 for(int j = 0; j < m; j ++) { 15 if(s1[i] == s2[j]) dp[i + 1][j + 1] = dp[i][j] + 1; 16 else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); 17 } 18 } 19 cout << dp[n][m] << endl; 20 } 21 return 0; 22 }