动态规划解LCS与LIS：算法详解与C++实现

1. 最长公共子序列LCS与最长递增子序列LIS概述在算法领域子序列问题一直是经典且实用的课题。最长公共子序列Longest Common Subsequence, LCS和最长递增子序列Longest Increasing Subsequence, LIS是两个密切相关但又各具特点的问题。LCS要解决的问题是给定两个序列找出它们共有的、最长的子序列。这里的子序列不需要连续只需要保持相对顺序。例如ABC和AC都是ABCD的子序列。LCS在文本相似度比较、版本控制、生物信息学中的DNA序列比对等领域有广泛应用。LIS则是针对单个序列寻找一个子序列使得元素严格递增且长度最长。比如序列[10, 9, 2, 5, 3, 7, 101, 18]的LIS是[2, 3, 7, 101]长度为4。LIS在任务调度、股票分析、路径规划等场景中都有重要应用。注意虽然LCS和LIS名称相似但它们是不同的问题。LCS处理两个序列的关系而LIS处理单个序列的性质。不过有趣的是它们可以通过动态规划这一共同的算法范式来解决。2. LCS问题详解与实现2.1 LCS的动态规划解法LCS的经典解法是动态规划其核心在于状态定义和状态转移方程。我们定义dp[i][j]表示序列A前i个元素和序列B前j个元素的LCS长度。状态转移方程分为两种情况当A[i] B[j]时dp[i][j] dp[i-1][j-1] 1当A[i] ! B[j]时dp[i][j] max(dp[i-1][j], dp[i][j-1])这个方程直观理解就是当当前元素匹配时LCS长度可以增加1当不匹配时我们需要考虑两种可能的前驱状态中的较大值。2.2 LCS的C实现#include iostream #include algorithm #include string using namespace std; int LCS(const string A, const string B) { int m A.length(), n B.length(); int dp[m1][n1] {0}; for (int i 1; i m; i) { for (int j 1; j n; j) { if (A[i-1] B[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[m][n]; } int main() { string A ABCBDAB; string B BDCABA; cout LCS length: LCS(A, B) endl; return 0; }2.3 LCS的空间优化上述实现使用了O(mn)的空间实际上可以优化到O(min(m,n))。我们只需要保留当前行和上一行的数据即可int LCS_optimized(const string A, const string B) { if (A.length() B.length()) return LCS_optimized(B, A); int m A.length(), n B.length(); int prev[n1] {0}; int curr[n1] {0}; for (int i 1; i m; i) { for (int j 1; j n; j) { if (A[i-1] B[j-1]) { curr[j] prev[j-1] 1; } else { curr[j] max(prev[j], curr[j-1]); } } swap(prev, curr); } return prev[n]; }3. LIS问题详解与实现3.1 LIS的三种解法LIS问题有多种解法各有优缺点动态规划法时间复杂度O(n²)空间复杂度O(n)贪心二分法时间复杂度O(nlogn)空间复杂度O(n)转化为LCS法将原序列排序去重后与原序列求LCS3.2 动态规划解法定义dp[i]为以第i个元素结尾的LIS长度。状态转移方程为 dp[i] max(dp[j] 1) for all j i and nums[j] nums[i]int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 1); int max_len 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } max_len max(max_len, dp[i]); } return max_len; }3.3 贪心二分法最优解维护一个数组tails其中tails[i]表示长度为i1的LIS的最小末尾元素。这个数组是单调递增的可以用二分查找优化。int lengthOfLIS_optimized(vectorint nums) { vectorint tails; for (int num : nums) { auto it lower_bound(tails.begin(), tails.end(), num); if (it tails.end()) { tails.push_back(num); } else { *it num; } } return tails.size(); }这种方法将时间复杂度降到了O(nlogn)是解决LIS问题的最优算法。4. 实际应用与变种问题4.1 LCS的应用场景文本相似度比较比较两段代码或文档的相似度版本控制系统Git等工具比较文件差异生物信息学DNA序列比对拼写检查寻找最接近的正确单词4.2 LIS的应用场景俄罗斯套娃信封问题二维的LIS问题最长递增路径矩阵中的最长递增路径任务调度寻找最多可以安排的不冲突任务股票分析寻找最长的价格上涨序列4.3 合唱队形问题这是一个经典的LIS变种问题要求找到一个位置使得左边是递增序列右边是递减序列。解法是对每个位置计算从左到右的LIS和从右到左的LDS最长递减子序列然后求和取最大值。int chorusFormation(vectorint heights) { int n heights.size(); vectorint lis(n, 1), lds(n, 1); // 计算从左到右的LIS for (int i 1; i n; i) { for (int j 0; j i; j) { if (heights[j] heights[i]) { lis[i] max(lis[i], lis[j] 1); } } } // 计算从右到左的LDS for (int i n-2; i 0; --i) { for (int j n-1; j i; --j) { if (heights[j] heights[i]) { lds[i] max(lds[i], lds[j] 1); } } } int max_len 0; for (int i 0; i n; i) { max_len max(max_len, lis[i] lds[i] - 1); } return n - max_len; }5. 常见问题与优化技巧5.1 LCS常见问题如何重建LCS而不仅仅是计算长度可以反向追踪dp表当A[i]B[j]时这个字符属于LCS然后移动到dp[i-1][j-1]否则移动到dp[i-1][j]和dp[i][j-1]中较大的那个。如何处理多个序列的LCS对于k个序列的LCS时间复杂度会上升到O(n^k)通常需要特殊的优化或近似算法。5.2 LIS常见问题如何重建LIS序列除了维护dp数组还需要维护一个parent数组记录前驱节点。如何处理非严格递增的LIS只需将比较条件从nums[j] nums[i]改为nums[j] nums[i]。5.3 性能优化技巧滚动数组优化对于LCS可以使用两行数组代替整个二维数组。离散化处理对于LIS如果数值范围很大可以先离散化。记忆化搜索有时递归记忆化的写法比迭代更直观。并行计算对于大规模数据可以考虑并行化部分计算。6. 算法扩展与进阶6.1 二维LIS问题如俄罗斯套娃信封问题需要先对一维排序然后在另一维上求LISint maxEnvelopes(vectorvectorint envelopes) { sort(envelopes.begin(), envelopes.end(), [](const auto a, const auto b) { return a[0] b[0] ? a[1] b[1] : a[0] b[0]; }); vectorint tails; for (const auto env : envelopes) { int h env[1]; auto it lower_bound(tails.begin(), tails.end(), h); if (it tails.end()) { tails.push_back(h); } else { *it h; } } return tails.size(); }6.2 带权值的LIS每个元素有权值求权值和最大的递增子序列int weightedLIS(vectorint nums, vectorint weights) { int n nums.size(); vectorint dp(weights.begin(), weights.end()); int max_sum dp[0]; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] weights[i]); } } max_sum max(max_sum, dp[i]); } return max_sum; }6.3 分治解法对于某些特殊情况的LIS问题可以考虑使用分治法将问题分解为更小的子问题。在实际工程应用中选择哪种算法取决于具体场景和数据规模。对于小规模数据简单的动态规划就足够对于大规模数据则需要使用更高效的算法如贪心二分。