1、题目大意

我们称序列Z=是序列X=的子序列当且仅当存在严格上升的序列,使得对j=1,2,...,k, 有xij=zj。比如Z= 是X=的子序列。
现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列 Z,使得Z既是X的子序列也是Y的子序列。

2、对最长公共子序列的感性认识

好,以字符串abcfbc 和 abfcab 为例

表格中的数字嘛.....姑且解释为子串的最大公共子串的长度.最优子结构这个东西只能意会啊.

以图中标记的数字为例,它代表 子串 abc 和 abfcab的最长公共子串.

3、代码如下：

/*
 * 1159_1.cpp
 *
 *  Created on: 2013年7月31日
 *      Author: 黄东东
 *      为了能有章泽天这样的女朋友而不断努力。。。
 *
 */ 
 
#include   
#include   
 
int dp[1005][1005]; 
 
int max(int a, int b) { 
    return (a > b)   a : b; 
} 
 
int main() { 
 
    char stra[1001], strb[1001];//数组要开的足够大，否则会出错  
 
    int i, k; 
    while (scanf("%s%s", stra, strb) != EOF) { 
 
        int m = strlen(stra); 
        int n = strlen(strb); 
 
        memset(dp, 0, sizeof(dp)); 
 
        for (i = 1; i <= m; ++i) { 
            for (k = 1; k <= n; ++k) { 
                if (stra[i - 1] == strb[k - 1]) { 
                    dp[i][k] = dp[i - 1][k - 1] + 1; 
                } else { 
                    dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]); 
                } 
            } 
        } 
 
        printf("%d\n", dp[m][n]); 
    } 
    return 0; 
} 

/*
 * 1159_1.cpp
 *
 *  Created on: 2013年7月31日
 *      Author: 黄东东
 *      为了能有章泽天这样的女朋友而不断努力。。。
 *
 */

#include 
#include 

int dp[1005][1005];

int max(int a, int b) {
 return (a > b)   a : b;
}

int main() {

 char stra[1001], strb[1001];//数组要开的足够大，否则会出错

 int i, k;
 while (scanf("%s%s", stra, strb) != EOF) {

  int m = strlen(stra);
  int n = strlen(strb);

  memset(dp, 0, sizeof(dp));

  for (i = 1; i <= m; ++i) {
   for (k = 1; k <= n; ++k) {
    if (stra[i - 1] == strb[k - 1]) {
     dp[i][k] = dp[i - 1][k - 1] + 1;
    } else {
     dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]);
    }
   }
  }

  printf("%d\n", dp[m][n]);
 }
 return 0;
}

以下是c++实现。其实都差不多

/*
 * 1159_2.cpp
 *
 *  Created on: 2013年7月31日
 *      Author: Administrator
 */ 
 
#include   
 
using namespace std; 
 
int dp[1005][1005]; 
 
int max(int a , int b){ 
    return (a>b) a:b; 
} 
int main() { 
 
    string stra, strb; 
 
    while (cin >> stra >> strb) { 
        int m = stra.length(); 
        int n = strb.length(); 
        for (int i = 1; i <= m; ++i) { 
            for (int k = 1; k <= n; ++k) { 
                if (stra[i - 1] == strb[k - 1]) { 
                    dp[i][k] = dp[i - 1][k - 1] + 1; 
                } else { 
                    dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]); 
                } 
            } 
        } 
 
 
        cout<

using namespace std;

int dp[1005][1005];

int max(int a , int b){
 return (a>b) a:b;
}
int main() {

 string stra, strb;

 while (cin >> stra >> strb) {
  int m = stra.length();
  int n = strb.length();
  for (int i = 1; i <= m; ++i) {
   for (int k = 1; k <= n; ++k) {
    if (stra[i - 1] == strb[k - 1]) {
     dp[i][k] = dp[i - 1][k - 1] + 1;
    } else {
     dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]);
    }
   }
  }


  cout<