‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者LCS模版最长公共子序列Longest Common Subsequence仅求长度若字符相等dp[i][j] dp[i-1][j-1] 1若字符不等dp[i][j] max(dp[i-1][j], dp[i][j-1])int longestCommonSubsequence(string text1, string text2) { int n text1.size(), m text2.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); 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]; }这里注意因为ij记录的是前s的i个字符和t的前j个字符中的公共子序列由于字符下标是从0开始的所以实际上i只记录到下标为i-1的数j也是同理所以if对比的时候记得是对比s[i-1]t[j-1];记得要减一回溯具体子序列在 DP 填表完成后从右下角(n, m)倒推回去string getLCS(string text1, string text2) { int n text1.size(), m text2.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); // 1. 填表 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]); } } // 2. 回溯构建 LCS 字符串 string lcs; int i n, j m; while (i 0 j 0) { // 如果字符相等它是LCS的一部分往左上移动 if (text1[i - 1] text2[j - 1]) { lcs.push_back(text1[i - 1]); i--; j--; } // 如果不相等走向数值较大的那个方向 else if (dp[i - 1][j] dp[i][j - 1]) { i--; } else { j--; } } reverse(lcs.begin(), lcs.end()); return lcs; }LIS最长上升子序列Longest Increasing Subsequence, LIS这个是求一个字符串中或者数组中最长上升的那个子序列元素可以一样的用upper_boundvectorinttail; for (int i 0; i arr.size(); i) { int x arr[i]; auto it upper_bound(tail.begin(), tail.end(), x); if (it tail.end()) { tail.push_back(x); } else *it x; } cout tail.size() endl;这个是求arr数组的最长可以一样元素的最长子序列元素不可以一样的用lower_boundvectorinttailb; for (int i 0; i arr.size(); i) { int x arr[i]; auto it lower_bound(tailb.begin(), tailb.end(), x); if (it tailb.end()) { tailb.push_back(x); } else *it x; } cout tailb.size() endl;这个是求arr数组的最长子序列必须严格递增你想要的子序列类型应该用的函数原因严格递增不能相等lower_bound找第一个 x的位置会替换掉相等的元素阻止重复非严格递增允许相等upper_bound找第一个 x的位置保留相等的元素允许重复注意里面的操作都是关于tail数组的操作tail数组就是记录最长子序列元素的数组而且是保证里面的每个值尽可能小