判断题 偏易
#19774

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

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

未登录也能判分,登录后才会记录
答案与解析
正确答案:对
解析
使用动态规划求解最长公共子序列时,状态转移依赖于前一行和当前行的值。通过滚动数组技术,仅保留当前行和上一行的状态,将二维DP表压缩为两个一维数组或单个一维数组循环更新,从而减少空间占用。每次遍历中,依据序列元素是否相等更新当前状态,覆盖旧行数据以实现空间复用。该方法将空间复杂度由O(mn)降至O(n),其中m和n分别为两序列长度。