最长公共子序列问题

最长公共子序列问题 递归与动态规划实现 最长公共子序列问题 递归与动态规划实现 注 另附有两个 cpp 文件 1 递归方法求最长公共子序列的长度 1 设有字符串 a 0 n b 0 m 下面就是递推公式 当数组 a 和 b 对应位置字符相同时 则直接求解下一个位置 当不同时取两种 情况中的较大数值 LCS I j 1 LCS i 1 j 1 a i b j 或者 MAX LCS I j 1 LCS i 1 j a i 不等于 b j include include include include using namespace std string lcsstr define N 30 int xlen ylen int c N N int maxlen int LCS char x char y string d int i int j int len if i 0 jmaxlen maxlen len lcsstr d return 0 xlen strlen x ylen strlen y if x i y j d x i d return c i j LCS x y d i 1 j 1 len 1 1 else return LCS x y d i 1 j len LCS x y d i j 1 len LCS x y d i 1 j len LCS x y d i j 1 len int main char s1 N char s2 N int i j num char s new char N string d double t tt cout 输 入 第 一 个 字 串 s1 i strlen s1 cout 输 入 第 二t个 字 串 o s2 j strlen s2 t clock num LCS s1 s2 d i 1 j 1 0 tt clock t cout num lcsstr endl cout 运 行D时 间 o tt endl system pause 以下是用递归实现输出最长公共子序列的运行截图 2 动态规划 2 动态规划求最长公共子序列的长度 动态规划采用二维数组来标识中间计算结果 避免重复的计算来提高效率 1 最长公共子序列的长度的动态规划方程 设有字符串 a 0 n b 0 m 下面就是递推公式 字符串 a 对应的是二维数组 num 的行 字符串 b 对应的是二维数组 num 的列 include include include using namespace std define k 50 int i j int c k k int LCS char a char b int L k int al strlen a int bl strlen b for i 0 i al i L i 0 0 for j 0 j bl j L 0 j 0 for i 0 i al i for j 0 jL i j 1 L i 1 j L i j 1 return L al bl char LCSchar char a char b char s int L k k int i strlen a int j strlen b int l LCS a b L s l 0 while l 0 if L i j L i 1 j i else if L i j L i j 1 j else s l a i 1 i j return s int main char s1 k char s2 k char s new char k int e double t tt char f cout 输 入 第 一 个 字 串 s1 cout 输 入 第 二t个 字 串 s2 t clock e LCS s1 s2 c f LCSchar s1 s2 s tt clock t cout e f endl cout 运 行D时 间 o tt endl delete s system pause 下面是用动态规划算法 LCS1 运行得到的测试数据截图 为了使测试更具说服力 我又用了两组更长更复杂的数据来测试 结果动态规划的时间仍 为趋向 0 而用递归算法 LCS2 CPP 则很长时间得不到结果 截不到图 由以上数据我绘制了一幅运行时间随着输入子串的长度增大而增大的走势图 蓝色的是由递归算法数据画成 绿色线由动态规划线画成