算法

思路：
1、状态表示f [ i ] [ j ]
集合表示：f [ i ] [ j ] 所有A[ 1 - i ] ,与B[ 1 - j ] 的公共子序列的集合
属性： 最大值
2、状态计算
f [ i ] [ j ] 包含和前面的四种状态，a[i], b[j] 选不选有 00， 01， 10 ，11四种状态。
00： f [ i - 1 ] [ j - 1 ]
01：理论是不能有ai，必须有bj。而f [ i - 1 ] [ j ] 包含两种，一种是没有ai，没有bj；一种是没有ai，有bj；而第一种情况恰好是00的情况，所以这种是包含在我们本来的范围之内，可以用f [ i - 1 ] [ j ] 表示
10：同上，f [ i ] [ j - 1 ]
11： f [ i - 1 ] [ j - 1 ] + 1

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
char a[N],b[N];
int f[N][N];

int main()
{   //数据读入
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= m; i ++) cin >> b[i];

    //dp模板
    for(int i = 1; i <= n; i ++)
    {   
        for(int j = 1; j <= m; j ++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);//01和10的情况 
            if(a[i] == b[j])//11的情况
            {
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}