字符串知识（LCS，LIS）区分总结归纳

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者标准 LCS 模版二维 DP#includeiostream #includevector #includestring using namespace std; int LCS(string s1, string s2) { int n s1.size(), m s2.size(); // dp[i][j] 表示 s1前i个字符 与 s2前j个字符 的LCS长度 vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { if (s1[i - 1] s2[j - 1]) { // 字符相同从左上角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]; // 最终答案 }理解不了可以强行记住dp[i][j]的含义s1的前i个字符与s2的前j个字符的最长公共子序列长度情况 1字符相同s1[i-1] s2[j-1]说明当前字符可以加入公共子序列长度 之前状态dp[i-1][j-1] 1对应在表格中就是从左上角转移过来情况 2字符不同s1[i-1] ! s2[j-1]当前字符不能同时使用长度 从左边dp[i][j-1]或上边dp[i-1][j]继承最大值相当于跳过s1的当前字符或跳过s2的当前字符举例演示假设s1 abcdes2 aceDP 表格构建过程∅ace∅0000a0111b0111c0122d0122e0123例如#includeiostream #includevector #includealgorithm using namespace std; int main() { string s; cin s; int n s.size(); string t s; reverse(s.begin(), s.end()); vectorvectorintdp(n 1, vectorint(n1,0)); for (int i 1; i n; i) { for (int j 1; j n; j) { if (s[i - 1] t[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } cout n - dp[n][n] endl; return 0; }LIS最长上升子序列标准模版int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; // tails[k] 表示长度为 k1 的上升子序列的最小末尾元素 vectorint tails; for (int x : nums) { // 在 tails 中找第一个 x 的位置 auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { // x 比所有末尾都大可以延长最长子序列 tails.push_back(x); } else { // 替换掉第一个 x 的元素保持末尾尽可能小 *it x; } } return tails.size(); }两种情况情况操作含义it tails.end()tails.push_back(x)x比所有现有末尾都大可以延长最长上升子序列it ! tails.end()*it x找到一个比x大的末尾用x替换它让该长度的末尾更小变种输出具体序列vectorint getLIS(vectorint nums) { int n nums.size(); vectorint tails; // 记录最小末尾 vectorint pos(n); // pos[i] 记录 nums[i] 在 tails 中的位置 vectorint prev(n, -1); // prev[i] 记录 nums[i] 的前驱索引 for (int i 0; i n; i) { auto it lower_bound(tails.begin(), tails.end(), nums[i]); int idx it - tails.begin(); if (it tails.end()) { tails.push_back(nums[i]); } else { *it nums[i]; } pos[i] idx; if (idx 0) { // 找前一个位置的元素倒序遍历找 pos[j] idx-1 的第一个 for (int j i - 1; j 0; j--) { if (pos[j] idx - 1 nums[j] nums[i]) { prev[i] j; break; } } } } // 回溯构造 LIS vectorint result; int len tails.size(); for (int i n - 1; i 0; i--) { if (pos[i] len - 1) { int cur i; while (cur ! -1) { result.push_back(nums[cur]); cur prev[cur]; } reverse(result.begin(), result.end()); break; } } return result; }例如#includeiostream #includevector #includealgorithm using namespace std; int main() { vectorintarr; int x; while (cin x) { arr.push_back(x); } reverse(arr.begin(), arr.end()); vectorinttail; 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; vectorinttaila; reverse(arr.begin(), arr.end()); for (int i 0; i arr.size(); i) { int x arr[i]; auto it lower_bound(taila.begin(), taila.end(), x); if (it taila.end()) { taila.push_back(x); } else *it x; } cout taila.size() endl; return 0; }lower_bound找第一个 x的位置。用于严格递增子序列。upper_bound找第一个 x的位置。用于非严格递增允许相等子序列。