思路

• 限制
  • 公共
  • 最长
• 集合：所有a[1~i]与b[1~j]的公共子序列的集合
• 状态计算：
  • a[i]和b[j]是否在子序列里，有四种情况
  • 1、（00）不包含a[i]和b[j]
    • f[i - 1][j - 1]
  • 2、 （01）不包含a[i]包含b[j]
    • （思维错误）f[i - 1][j],因为a(1~i-1),b(1~j),b[j]是不一定被选的
    • 求最大值，重复是无所谓的，只要不遗漏就可以，所以f[i - 1][j]
      • f[i - 1][j]是包含这种情况的所有方案的，虽然还包含其他方案，但不影响
  • 3、（10） 包含a[i]不包含b[j]
    • f[i][j - 1]
  • 4、（11）a[i]和b[j]都是两子序列的最后一个字符，因此a[i] = b[j]
    • f(i - 1, j - 1) + 1
  • f[i][j - 1]和f[i - 1][j]相互有重复，但是没关系，只要能覆盖就可以
  • 1已经包含在3和4里了，所有不用写，可以只考虑2、3、4三种情况
  • 

#include <iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n >> m >> a + 1 >> b + 1;

    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]);
            f[i][j] = max(f[i][j - 1], f[i][j]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

    cout << f[n][m] << endl;
    return 0;

}