f(i,j)
集合： A的前i个字符串 和 B中前j个字符串的 所有公共子序列的集合
属性 ： 该集合中最长公共子序列的长度

集合划分 : 以第i个 和第j个 字母在不在公共子序列中划分 ，共有4种情况
为了方便表示 以0表示不再 以1表示在

备注: 划分集合的依据是 不复不漏 但是计算最值是 划分的集合之间可以有重叠 但是肯定不会超出原本整个集合的界限

所以 只要计算出 01 10 11 这三种集合中的最大值即可

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010;

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

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

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j ++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if(a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }

    cout << dp[n][m] << endl;

    return 0;
}