👉从记忆化搜索到打表
问题引入
子序列是什么？例如对于字符串"woaini"，wan是其一个子序列，woain也是一个子序列。子序列不要求连续性,而子串必须是连续的。
于是我们想到这种方法可以用暴力递归来做，即尝试所有的公共子序列，然后取里面最长的，但是我们追求更高的效率，我们发先最长公共子序列问题有最优子结构，这个问题可以分解称为更小的问题，同时，子问题的答案可被重复使用，也就是说更高级别的子问题会重用更小子问题的解。如此，我们便可以通过记忆化搜索的方式改进递归
下面我们先来推 递归需要满足的条件（也就是列举可能性）
- 假设两个字符串s1, s2。当其中一个串的长度为0时，公共子序列的长度肯定为0
- 假设s1的第i个字符与s2的第j个字符相等时，最长子序列等于s1的第i-1个字符与s2的第j-1个字符最长子序列长度+1
- 假设s1的第i个字符与s2的第j个字符不相等时，最长子序列等于s1的第i个字符与s2的第j-1个字符最长子序列长度或s1的第i-1个字符与s2的第j个字符最长子序列长度中最大那一个
👉记忆化搜索
代码如下：
int process(string& str1, string& str2, int i, int j) {//以i，j为结尾下标 if (dp[i][j])//如果该位置的答案已经被求解出来，那么直接返回答案 { return dp[i][j]; } if (i == 0 && j == 0) {//分析各种边界条件（当两字符串其中一个或者都只剩下一个字符时，分析两者相等与不等的情况），找递归出口 if (str1[i] == str2[j]) { dp[i][j] = 1; } flag[i][j] = 1;//记录路径（如果相同就标为1，而因为这里两个字符串都只剩下一个字符， //所以无论标为1,2,还是3（即无论向哪走）都会结束，所以这里标几也就不重要了） return dp[i][j]; } else if (i == 0) { if (str1[i] == str2[j]) { dp[i][j] = 1; flag[i][j] = 1; return dp[i][j]; } else {//如果不同，则标为2（往左走） dp[i][j] = process(str1, str2, i, j - 1); flag[i][j] = 2; return dp[i][j]; } } else if (j == 0) { if (str1[i] == str2[j]) { flag[i][j] = 1; dp[i][j] = 1; return dp[i][j]; } else {//标为3（往右走） dp[i][j] = process(str1, str2, i - 1, j); flag[i][j] = 3; return dp[i][j]; } } int p1 = process(str1, str2, i, j - 1); int p2 = process(str1, str2, i - 1, j); int p3 = 0; if (str1[i] == str2[j]) { p3 = process(str1, str2, i - 1, j - 1) + 1; flag[i][j] = 1;//如果相等就先标上 } dp[i][j] = max(max(p1, p2), p3); if (!flag[i][j]) {//这里如果成立，这说明之前没标上，也就是两个字符不相等，那么就找下一步长度最大的标上 if (p2 >= p1)flag[i][j] = 3; else flag[i][j] = 2; } return dp[i][j]; } int longestCommonSubsequence(string text1, string text2) { dp.resize(text1.size(), vector<int>(text2.size())); flag.resize(text1.size(), vector<int>(text2.size())); string path = ""; int ans = process(text1, text2, text1.size() - 1, text2.size() - 1); return ans; } int main() { cout << longestCommonSubsequence("YiQingTuiSan", "YIQINGTUISAN") << endl; return 0; }
然而我们并不满足只是记忆化搜索，我们追求极致的效率，同时我们发现记忆化搜索的本质其实就是个打表，那为什么我们不从上帝视角根据位置依赖自己把这张表打出来呢？ 于是便有了所谓的动态规划
👉动态规划
void LCS() { for(int i = 1; i <= len1; i++){ for(int j = 1; j <= len2; j++){ if(s1[i-1] == s2[j-1]){ //注：此处的s1与s2序列是从s1[0]与s2[0]开始的 c[i][j] = c[i-1][j-1] + 1; } else{ c[i][j] = max(c[i][j-1], c[i-1][j]) ; } } } }
更多内容请听下一回讲解
最长公共子序列 之 输出路径版
🌹写在最后💖： 路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！🌹🌹🌹
