题解 | #最长公共子序列(二)#
最长公共子序列(二)
https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11
2022.0814算法第21题最长公共子序列(二)
动态规划问题，但是做的比较少还没有理解动态规划的主要套路。
这个需要先求解一个二维矩阵，求解出最长子序列的长度，然后根据指示方向取出最长子序列。
第一步需要求解最长子序列长度，并记录当前字符的方向，也就是最长子序列的取值位置方向。
if(s1[i-1]==s2.at(j-1)){
res[i][j]=res[i-1][j-1]+1;
direc[i][j]=1;
}
else{
res[i][j]=max(res[i-1][j],res[i][j-1]);
if(res[i-1][j]>res[i][j-1]){
direc[i][j]=2;
}else
direc[i][j]=3;
}
状态转移方程，用于更新最长子序列长度并记录方向。
根据方向进行寻找子序列，可以通过递归和循环的方式。
递归比较好理解，每次递归走一步，每个位置都需要重复之前的操作。
string ans(string s1,int i,int j,vector<vector<int>> &dires){
string res="";
if(i==0||j==0){
return res;
}
if(dires[i][j]==1){
//这里的先后顺序不能乱,如果顺序颠倒，那么结果就是倒叙了。
res+=ans(s1,i-1,j-1,dires);
res+=s1[i-1];
}
else if(dires[i][j]==2)
res+=ans(s1,i-1,j,dires);
else if (dires[i][j]==3)
res+=ans(s1,i,j-1,dires);
return res;
}
循环也不算复杂，只不过得到的是倒叙，需要进行翻转。
int i=s1.size(),j=s2.size();
while(i>0&&j>0){
if(direc[i][j]==1){
s.push_back(s1[i-1]);
i--;
j--;
}
else if (direc[i][j]==2)
i--;
else if (direc[i][j]==3)
j--;
}
reverse(s.begin(), s.end());
最后返回可以判断是否为空
return s!=""?s:"-1";
