动态规划解决最长公共子序列,动态规划最长公共子序列问题
描述给定str1和str2的两个字符串的最长公共子序列。如果最长公共子序列为空，则返回“-1”。目前，在给定的数据中只有一个最长的公共子序列。
数据范围：需求：空间复杂度，时间复杂度
示例1输入：
1A2C3D4B56 ， B1D23A456A 返回值：
123456 示例2输入：
Abc ， def 返回值：
-1 示例3输入：
Abc ， abc 返回值：
“Abc”示例4输入：
Ab ，返回值：
“-1”问题需要最长的公共子序列，因此所有字母相同且方向递增的字母都可以包含在统计中。另外，因为要返回最长的序列，所以不仅要问最长序列的长度，还要记录动态规划的路径。
动态规划递归的实现思想如下：
动态规划问题，总是逃不出以下几个步骤：
确定dp数组表示的意义：假设s1和s2的长度分别为m和n，我们用数组dp[i][k]表示s1的前I个字符和s2的前k个字符的最长公共长度，用m[i][k]记录每个选择的方向来确定初始条件：dp[0][i]，dp[i][0]都为0。那么dp[i][k]=dp[i-1][k-1] 1。此时设m[i][k]=1，表示从s1[i-1]和s2[k-1]子串递归如果s1[i]！=s2[k]，则dp[i][k]等于dp[i-1][k]或dp[i][k-1]中的一个。当m[i][k]取2时，表示来自s1[i-1] s2[k]，取3表示来自S1 [
传递参数时，尽量使用引用，减少不必要的计算。比如用边界条件提前返回，否则不给内存和时间~ ~其实上面的路径记录表M可以省略，因为我们可以通过dp[i][k]和dp[i][k-1]的大小关系判断路径方向码如下：
#包含位/标准数据。h
//动态编程问题，总是逃不出以下几个步骤：
//1.确定dp数组所表示的意义：假设s1和s2的长度分别为m和n，我们用arr[i][k]数组来表示s1的前I个字符和s2的前k个字符的最长公共长度。
//2.确定初始条件：arr[0][i]和arr[i][0]的值都是0。
//3.确定递归关系：
//1.如果s1[i]==s2[k]，那么arr[i][k]=arr[i-1][k-1] 1
//2.如果s1[i]！=s2[k]，则arr[i][k]等于arr[i-1][k]或arr[i][k-1]。
//4.arr[m][n]是最长子序列的长度。
//5.但是题目要求返回最长序列的内容，所以我们需要另外一个表格来记录我们在推导过程中的方向选择。
//1.我们使用表[i][k]来指示在上一步中到达当前时间时的方向选择。
//2.如果s1[i]==s2[k]，则表示应该将s1[i]添加到最长的序列中。
//3.如果s1[i]！=s2[k]，那么最长的自夸应该产生在s1[i-1]，s2[k]或者s1[i]，s2[k-1]，
//这个问题可以通过递归来解决
//注：对于arr[i][k]，我们在思考问题的时候，应该认为arr小于I和k的所有值都是已知的。
std:string walk(std:string s1，std:string s2，int i，int k，std:vector std:vector int m)
{
如果(i==0 k==0)
{
返回“”；
}
如果(m[i][k]==1)
{
回程步行(s1，s2，i - 1，k - 1，m)。append(1，S1[I-1])；
}
如果(m[i][k]==2)
{
回程步行(s1，s2，i - 1，k，m)；
}
回程步行(s1，s2，I，k - 1，m)；
}
标准：字符串LCS(标准：字符串s1，标准：字符串s2)
{
if (s1.empty() s2.empty())
{
return -1 ；
}
STD:vector STD:vector int DP(S1 . size()1，std:vector int (s2.size() 1，0))；
STD:vector STD:vector int m(S1 . size()1，std:vector int (s2.size() 1，0))；
for(int I=1；I=S1 . size()；我)
{
for(int k=1；k=S2 . size()；k)
{
if (s1[i - 1]==s2[k - 1])
{
DP[I][k]=DP[I-1][k-1]1；
m[I][k]=1；
}
其他
{
if (dp[i - 1][k] dp[i][k - 1])
{
DP[I][k]=DP[I-1][k]；
m[I][k]=2；
}
其他
{
DP[I][k]=DP[I][k-1]；
m[I][k]=3；
}
}
}
}
STD:string ans { -1 }；
if (dp[s1.size()][s2.size()]！=0)
{
ans=walk(s1，s2，s1.size()，s2.size()，m)；
}
返回ans
}动态规划栈的实现以下代码由Niuke.com官方提供。
类别解决方案{
公共：
字符串LCS(字符串s1，字符串s2) {
//只要有空字符串，就没有子序列
if(S1 . length()==0 S2 . length()==0)
return -1 ；
int len 1=S1 . length()；
int len 2=S2 . length()；
//dp[i][j]表示从第一个字符串到第I位和第二个字符串到第j位的最长公共子序列长度。
向量向量int dp(len1 1，向量int (len2 1，0))；
//遍历两个字符串每个位置的最长长度
for(int I=1；i=len1i ){
for(int j=1；j=len2j ){
//遇到两个相等的字符
if(s1[i - 1]==s2[j -1])
//从左上角开始
DP[I][j]=DP[I-1][j-1]1；
//遇到的两个字符不同
其他
//从左侧或顶部开始的最大值
dp[i][j]=max(dp[i - 1][j]，DP[I][j-1])；
}
}
//从动态编程数组的末尾开始
int i=len1，j=len2
堆栈字符；
while(dp[i][j]){
//从左侧方向
if(dp[i][j]==dp[i - 1][j])
I-；
//从上方
else if(dp[i][j]==dp[i][j - 1])
j-；
//从左上方向
else if(dp[i][j] dp[i - 1][j - 1]){
I-；
j-；
//只有左上方向是字符相等的情况。将它们堆叠起来，以相反的顺序使用。
s . push(S1[I])；
}
}
string RES=“”；
//拼接子序列
而(！s.empty()){
RES=s . top()；
s . pop()；
}
//如果两者完全不同，并且返回字符串为空，则将其更改为-1
返回res！= ?RES:“-1”；
}
};
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。