判断题 偏易
#16939

求两个长度为 n 序列的最长公共子序列(LCS)长度时,可以使用滚动数组将空间复杂度从 O(n²) 优化到 O(n) 。

求两个长度为 n 序列的最长公共子序列(LCS)长度时,可以使用滚动数组将空间复杂度从 O(n²)优化到 O(n)。

未登录也能判分,登录后才会记录
答案与解析
正确答案:对
解析
使用动态规划求解最长公共子序列时,状态转移依赖于前一行和当前行的值。通过滚动数组技术,仅保留当前行和前一行的状态,将二维状态表压缩为两个一维数组交替更新。每次遍历时根据索引奇偶性或模运算决定当前使用哪一行,从而实现空间复用。该方法使存储空间由O(n²)降至O(n),同时保持时间复杂度不变。