LeetCode 1143 最长公共子序列：C++ 解法空间优化至 O(min(m, n))

LeetCode 1143 最长公共子序列C 解法空间优化至 O(min(m, n))动态规划是算法面试中的常客而最长公共子序列LCS问题更是动态规划中的经典案例。本文将带你深入理解如何将传统的 O(m*n) 空间复杂度解法优化至 O(min(m, n))这种优化技巧在面试中往往能让你脱颖而出。1. 问题定义与基础解法最长公共子序列问题要求找出两个字符串中最长的子序列这个子序列不需要连续但必须保持相对顺序。例如ace 是 abcde 和 ace 的 LCS。传统的动态规划解法使用一个二维数组 dp[m1][n1]其中 dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度。状态转移方程为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]); }这种方法虽然直观但空间复杂度为 O(m*n)当字符串较长时会消耗大量内存。2. 空间优化思路观察状态转移方程可以发现计算 dp[i][j] 时只需要上一行的 dp[i-1][j-1] 和 dp[i-1][j]当前行的 dp[i][j-1]这意味着我们不需要存储整个二维数组只需要两行数据即可完成计算。进一步优化可以只使用一行数组加上一个额外变量来存储左上角的值。3. 优化实现细节以下是空间优化后的 C 实现int longestCommonSubsequence(string text1, string text2) { int m text1.size(), n text2.size(); if (m n) return longestCommonSubsequence(text2, text1); // 确保text2是较短的 vectorint dp(n 1, 0); for (int i 1; i m; i) { int prev 0; // 存储左上角的值 for (int j 1; j n; j) { int temp dp[j]; // 保存当前值下一轮会成为左上角 if (text1[i-1] text2[j-1]) { dp[j] prev 1; } else { dp[j] max(dp[j], dp[j-1]); } prev temp; } } return dp[n]; }这个实现的关键点在于只使用一维数组 dp[n1]prev 变量保存左上角的值即 dp[i-1][j-1]在更新 dp[j] 前保存其值作为下一轮的 prev4. 复杂度分析与对比让我们通过表格对比两种方法的复杂度方法时间复杂度空间复杂度传统二维数组O(m*n)O(m*n)滚动数组优化O(m*n)O(n)本文优化方法O(m*n)O(min(m, n))注意在实际编码中我们总是选择较短的字符串长度作为数组大小因此空间复杂度可以表示为 O(min(m, n))。5. 实际应用与面试技巧这种空间优化技巧不仅适用于 LCS 问题还可以推广到其他二维动态规划问题中。在面试中展示这种优化能力可以体现你对算法本质的深刻理解。常见面试问题可能包括为什么可以这样优化空间如何回溯找到具体的 LCS 而不仅仅是长度这种优化方法有哪些局限性对于回溯问题虽然空间优化后丢失了部分信息但我们仍可以通过以下方法解决先计算长度从后向前重建路径利用字符匹配和长度变化确定选择6. 扩展思考其他优化方向除了空间优化LCS 问题还有其他值得探索的优化方向并行计算优化由于动态规划表格的计算有特定的依赖关系可以设计并行算法近似算法对于超长字符串可以研究近似算法快速估计 LCS 长度特定场景优化当字符串有特殊结构如高度重复时可能有更优解法在实际工程应用中根据具体场景选择合适的算法变体往往比单纯追求理论最优解更重要。7. 代码实现中的陷阱与技巧在实现优化版本时有几个容易出错的细节需要注意// 常见陷阱1忘记初始化prev int prev 0; // 必须在外层循环内初始化 // 常见陷阱2temp保存时机错误 int temp dp[j]; // 必须在更新dp[j]前保存 // 技巧交换字符串顺序减少空间使用 if (m n) return longestCommonSubsequence(text2, text1);此外对于追求极致性能的场景可以考虑以下优化使用原生数组代替vector循环展开使用位运算加速比较然而在面试中清晰可读的代码通常比微优化更重要除非面试官特别要求。掌握了这种空间优化技巧你就能在面试中游刃有余地处理类似的动态规划问题展现出扎实的算法功底和优化意识。记住理解问题本质比记忆模板更重要这才是区分优秀工程师的关键。