ACM竞赛备战资料精选--动态规划之最长公共子序列（lcs）
动态规划之最长公共子序列(lcs)
最长公共子序列的定义是，一个数列z分别是已知数列的子序列(子序列不一定是连续序列，是在该序列中删去若干元素后得到的序列)，且是所有符合此条件序列中最长的，则z成为最长公共子序列lcs(Longest Common Subsequences)。有些地方则说公共子串就是要求连续的子序列，有些地方则不是，这里要注意区分。下面是完整实现代码。
#include
using namespace std;
void LCS_Length(char *x,char *y,int **b,int m,int n)
{
//c[i][j]表示x[i-1],y[j-1]之前公共子序列的长度,i表示x数组前进，j表示y数组前进
//不用c[i][j]表示x[i],y[j]之前公共子序列的长度是因为需要使用c[0][0]来表示没有公共子序列，
//即c[0][0]恒等于0，因此c数组最大下标为c[m+1][n+1]
int **c;
c=new int*[m+1];
for( int i=0;i=c[i][j-1])
{
c[i][j]=c[i-1][j];//当前最长公共子序列可以不需要x[i-1]
b[i][j]=-1;
}
//和上面
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
类似
else
{
c[i][j]=c[i][j-1];//当前最长公共子序列可以不需要y[j-1]
b[i][j]=1;
}
}
}
for(int i=0;i
本文档为【ACM竞赛备战资料精选--动态规划之最长公共子序列（lcs）】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483