LCR 095 最长公共子序列
https://leetcode.cn/problems/qJnOS7/description/
递归
class Solution {
public:
int max_len(string text1,int index1,string text2,int index2){
if(index1>=text1.size()) return 0;
if(index2>=text2.size()) return 0;
int next_index = 0;
bool flag = false;
for(int i = index1;i<text1.size();i++){
next_index = i;
if(text1[i]==text2[index2]){
flag =true;
break;
}
}
if(flag){
int you = 1+max_len(text1,next_index+1,text2,index2+1);
int wu = max_len(text1,index1,text2,index2+1);
return max(you,wu);
}
return max_len(text1,index1,text2,index2+1);
}
int longestCommonSubsequence(string text1, string text2) {
return max_len(text1,0,text2,0);
}
};
这里犯了一个错误，就是这个for循环，在本层不应该使用for循环找到下层有效位置，而是直接令 next_index = index1+1 。
您可能选择使用 `for` 循环来查找下一个匹配字符，是因为您试图找到 `text1` 中从 `index1` 开始的第一个与 `text2[index2]` 匹配的字符位置。这种方法在某些情况下是有效的，但在递归函数中使用这种方式可能会导致代码结构变得复杂，也容易出现逻辑错误。
递归函数本身具有自我调用的特性，通常能够更自然地处理索引的递增和比较，而不需要显式地使用循环来搜索。使用递归时，重点是正确地定义递归的基本情况和递归步骤，而不是通过循环来手动控制迭代过程。
在处理字符串的问题中，如寻找最长公共子序列，递归函数能够更清晰地表达问题的解决方法。通过直接传递 `index1` 和 `index2` 的方式，递归调用可以自然地处理字符串的字符比较和递增，而不需要额外的迭代或查找操作。
总结来说，使用递归函数时，尽量避免使用循环来查找下一个匹配字符，而应该利用递归的自我调用特性来处理索引的移动和字符的比较，以保持代码简洁和逻辑清晰。
class Solution {
public:
vector<vector<int>> dp;
int max_len(string& text1, int index1, string& text2, int index2) {
if (index1 >= text1.size() || index2 >= text2.size())
return 0;
if (dp[index1][index2] != -1)
return dp[index1][index2];
if (text1[index1] == text2[index2]) {
dp[index1][index2] = 1 + max_len(text1, index1 + 1, text2, index2 + 1);
} else {
dp[index1][index2] = max(max_len(text1, index1 + 1, text2, index2), max_len(text1, index1, text2, index2 + 1));
}
return dp[index1][index2];
}
int longestCommonSubsequence(string text1, string text2) {
dp = vector<vector<int>>(text1.size(), vector<int>(text2.size(), -1));
return max_len(text1, 0, text2, 0);
}
};
- 如果两个字符串在当前位置的字符不匹配，就需要考虑跳过其中一个字符串的当前字符，然后比较剩余部分。具体来说：
- 可以跳过
text2的当前字符，即max_len(text1，index1，text2，index2 + 1)。 - 或者可以跳过
text1的当前字符，即max_len(text1，index1 + 1，text2，index2)。 - 在这两种情况下，递归调用分别探索了跳过一个字符后的可能性，并通过比较返回其中较大的结果。
回溯
在将回溯变为动态规划时很困难，相比之下选和不选的问题较为简单。
class Solution {
public:
vector<vector<int>> dp;
int max_sub(string text1,int index1,string text2,int index2){
if(index1==text1.size()||index2==text2.size()) return 0;
if(dp[index1][index2]!=-1) return dp[index1][index2];
int count = 0;
for(int i = index1;i<text1.size();i++){
for(int j = index2;j<text2.size();j++){
if(text1[i]==text2[j]){
int remian = max_sub(text1,i+1,text2,j+1);
count = max(remian+1,count);
}
}
}
dp[index1][index2] = count;
return count;
}
int longestCommonSubsequence(string text1, string text2) {
dp = vector<vector<int>>(text1.size(), vector<int>(text2.size(), -1));
return max_sub(text1,0,text2,0);
}
};
选和不选
https://www.bilibili.com/video/BV1TM4y1o7ug/
看成子集问题，本质是选不选的问题
对于两个序列的开头两个字母：x 和 y 是否要加到公共子序列种，分别有选和不选一共有4种情况。
-
选x，选y，这时要求其相等，否则不能加到子序列种。
-
不选x，选y
-
选x，不选y
-
不选x，不选y，这种情况子问题和第一种一样，但是第一种加了个1，所以这种情况一定小于选x和选y
或者说类似之前的回溯问题，假设有全局变量lcs 是一个数组；本层是 选一个字母加入到lcs中，那么本层有几种情况呢：有可能两个数相等，那么就直接加入到lcs，index分别后移一位；有可能不等，那么本层就不会加入到lcs，那下一层如何调用呢，这里x 和y 必然有一个要被丢弃掉：1.只丢弃其中一个 2.都丢弃，但是这样index分别后移一位，这和两数相等的情况是一样的，但是本层得到的值比之前的少一个，省略掉了。
class Solution {
public:
int max_sub(string text1,int index1,string text2,int index2){
if(index1==text1.size()||index2==text2.size()) return 0;
//选x，选y
if(text1[index1]==text2[index2]) return 1+max_sub(text1,index1+1,text2,index2+1);
// 不相等，那么最后的lcs中必然不可能同时存在这两个，需要去掉一个
// index2+1就是 text2 中的去掉了一个。
return max(max_sub(text1,index1,text2,index2+1),max_sub(text1,index1+1,text2,index2));
//都不选就直接省略掉了。
}
int longestCommonSubsequence(string text1, string text2) {
return max_sub(text1,0,text2,0);
}
};
动规
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.length(), m = text2.length();
int dp[n + 1][m + 1];
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n; i++)
for (int j = 1; j <=m ; j++)
if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
return dp[n][m];
}
};