动态规划最长公共子序列

目录

1. 最长公共子序列简介
2. 举例说明并分析
3. 代码块
4. 测试结果

最长公共子序列简介

从一个给定的序列中删除若干元素后所获得的新序列为该原始序列的一个子序列；具体来说，则是指存在一组严格递增的下标集合{i₀,i₁,…,i_{k−1}}},使得对于每一个j∈{0,1,…,k−1}都有Zⱼ=X_{iⱼ}。比如取Z={B,C,D,B}作为X={A,B,C,B,D,A,B}的一个例证，则对应的索引集为{1,2,4,6}}。

如何将最长公共子序列问题分解为子问题？设A=“a₀,a₁,…,aₘ₋₁”以及B=“b₀,b₁,…,bₘ₋₁”；再设Z=“z₀,z₁,…,zₖ₋₁”为它们的最长公共子序列。请问如何求解其长度？

举例说明并分析

穷举搜索法是一种直观易懂的方法。它通过遍历所有可能的候选解来寻找最优解。具体来说，在给定两个字符串X和Y的情况下，在所有可能的X的子序列中寻找那些同时也是Y的有效子序列。通过这种方法可以判断其是否为X与Y的一个共同子序列。同时，在这一过程中记录下最长的共同子序列。所有这些子序列都被逐一检查后，则可确定X与Y的最大长度公共子序列。每个这样的子序列都对应于下标集合{0,1,2,…,m-1}的一个特定组合。因此总共有2^m个不同的可能组合。这使得穷举法的时间复杂度达到了指数级