蓝桥杯算法提高VIP-最长公共子序列

solution

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	string a, b;
	cin >> a >> b;
	a = " " + a;
	b = " " + b;
	int la = a.size(), lb = b.size();
	int dp[la + 1][lb + 1];
	for(int i = 0; i < la; i++){//边界，当i==0或j==0时，和空串的公共子序列一定为0
		dp[i][0] = 0;
	} 
	for(int i = 0; i < lb; i++){
		dp[0][i] = 0;
	}
	for(int i = 1; i < la; i++){//状态转移方程
		for(int j = 1; j < lb; j++){
			if(a[i] == b[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	printf("%d", dp[la - 1][lb - 1]);
	return 0;
}