题意

给两个字符串，求它们最长的公共子序列的长度

思路

$a_{i,j}$ 存的是 x 以 i 结尾和 y 以 j 结尾的最长的公共子序列的长度。

所以在没有相同的字符时，也要继承前面的结果；在有相同字符时，再加 1 并比较大小

代码

#include <bits/stdc++.h>
using namespace std;
string x,y;
int a[1005][1005];
int main(int argc, char **argv){
	cin >> x >> y;
	for(int i = 1;i <= x.size();i++){
		for (int j = 1;j <= y.size();j++){
			int si = i - 1,sj = j - 1;	// 为了方便演示，字符串用另一种 ij
			// a[i][j] 存 x 第 i 个结尾和 y 第 j 个结尾的最长公共子序列长度
			a[i][j] = max(a[i - 1][j],a[i][j - 1]);	// 继承最长子序列更大的那个
			if (x[si] == y[sj]){	// 有相同的字符，加 1 并比较
				a[i][j] = max(a[i][j],a[i - 1][j - 1] + 1);	// 取更大的
			}
		}
	}
	cout << a[x.size()][y.size()];
	return 0;
}

长但是优美的代码

优美的代码具有对称性，简约感

#include<iostream>
using namespace std;
int main(){
	string a,b;
	cin>>a>>b;
	int lena=a.size(),lenb=b.size();
	int f[lena+1][lenb+1]={};
	for(int i=0;i<lena;i++)
	{
		for(int j=0;j<lenb;j++)
		{
			if(i&&j)
			{
				if(a[i]==b[j])
				{
					f[i][j]=f[i-1][j-1]+1;
				}
				else
				{
					f[i][j]=max(f[i][j-1],f[i-1][j]);
				}
			}
			else
			{
				if(a[i]==b[j])
				{
					f[i][j]=1; 
				}
				else
				{
					if(i)
					{
						f[i][j]=f[i-1][j];
					}
					if(j)
					{
						f[i][j]=f[i][j-1];
					}
				}
			}
		}
	}
	cout<<f[lena-1][lenb-1];
}

#include <bits/stdc++.h>
using namespace std;
string x,y;
int a[10000][10000];
int main(){
    cin>>x>>y;
    for(int i=1;i<=x.size();i++){
        for(int j=1;j<=y.size();j++){
            int pp=i-1,anan=j-1;
            a[i][j]=max(a[i][j-1],a[i-1][j]);
            if(x[pp]==y[anan]){
                a[i][j]=max(a[i][j],a[i-1][j-1]+1);
            }

        }
    }
    cout<<a[x.size()][y.size()];
}