LCS

• 状态：$f_{i,j}$ 表示 $A[1...i],B[1...j]$ 最长公共子序列长度。
• 转移：

$$f_{i,j}=\begin{cases} f_{i-1,j-1}+1 , &A_i = B_j\\ max\{f_{i-1,j}, f_{i,j-1}\} , &A_i \neq B_j\\ \end{cases} $$

• 目标：$res=f_{n,m}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int f[N][N];

int main(int argc, char* argv[]) {
    string a, b;
    while (cin >> a >> b) {
        memset(f, 0, sizeof f);
        a = '1'+a, b='1'+b;
        int n = a.size()-1, m = b.size()-1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (a[i] == b[j])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        cout << f[n][m] << endl;
    }
    return 0;
}