LCS及其应用（最长公共子序列）

d p [ i ] [ j ] dp[i][j] dp[i][j]表示

a a a串的前 i i i个与b串的前 j j j个的最长公共子序列的长度。则：

d p [ i ] [ j ] = { m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) a [ i ] ! = b [ i ] d p [ i − 1 ] [ j − 1 ] + 1 a [ i ] = b [ i ] dp[i][j]= \begin{cases} max(dp[i-1][j],dp[i][j-1])& a[i]!=b[i]\\ dp[i-1][j-1]+1& a[i]=b[i] \end{cases} dp[i][j]={max(dp[i−1][j],dp[i][j−1])dp[i−1][j−1]+1​a[i]!=b[i]a[i]=b[i]​

for(int i=1;i<=len;i++) {
				for(int j=1;j<=len;j++) {
					if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1]+1;
					else dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}