求最长公共子序列(DP算法)

思路:

s1 =

s2 =

若它们的最长公共子序列为 s3 =

则:

若xn == ym:

gk为xn和ym的最长公共子序列LCS的最后一个元素&&g(k-1)为xn-1和ym-1的LCS的元素

此时:lcs[xn][ym] = lcs[xn-1][ym-1] + 1.(即在len(zk-1)的长度的基础上长度 + 1)

若xn != ym:

则gk为(xn,ym-1)或 (xn-1,ym)的最长子序列的一个元素

此时:lcs[xn][ym] = max(len(lcs[xn][ym-1]) , len(lcs[xn-1][ym]) )+ 1

综上利用动态规划方程:

#include
#include
#include
#include
#include
using namespace std;
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	int max_sum = max(s1.size(),s2.size());
	int dp[max_sum + 4][max_sum + 4];
	memset(dp,0,sizeof(dp));
	for(int i = 1;i 

 

本文由 @陈奕天[Vip] 发布于 职涯宝 ,未经作者许可,禁止转载,欢迎您分享文章

发表评论

登录后才能评论
小程序
小程序
微信客服
微信客服
QQ客服 建站服务
分享本页
返回顶部