给定两个字符串，求它们最长公共子序列的长度。

例如：

s = "abcd", t = "becd"

输出3("bcd")

利用动态规划求解

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7  8 char s[102],t[102]; 9 int dp[102][102];10 11 int main(int argc, char const *argv[])12 {13     //freopen("input.txt","r",stdin);14     while(scanf("%s %s",s,t) != EOF) {15         int n = strlen(s);16         int m = strlen(t);17         memset(dp, 0, sizeof(dp));18         for(int i = 0; i < n; i++) { 19             for(int j = 0; j < m; j++) {20                 if(s[i] == t[j]) {21                     dp[i+1][j+1] = dp[i][j] + 1;22                 }23                 else {24                     dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);25                 }26             }27         }28         printf("%d\n",dp[n][m]);29     }30     return 0;31 }