判断题
偏易
#19753
求两个序列的最长公共子序列(LCS)时,使用滚动数组优化空间后,仍然可以还原出具体的LCS序列。
求两个序列的最长公共子序列(LCS)时,使用滚动数组优化空间后,仍然可以还原出具体的LCS序列。
答案与解析
正确答案:错
解析
使用动态规划求解最长公共子序列时,状态转移基于前一行或当前行的值更新。滚动数组通过只保存必要行(如当前行和上一行)来减少空间占用。还原具体LCS序列需回溯路径,可在计算过程中记录决策位置或利用原序列与滚动数组状态逆推匹配点。匹配字符的位置可通过比较当前状态与前一状态差异确定,逐步向前追踪至序列起始。此过程不依赖完整二维表,仅需当前维护的压缩状态及原始输入序列即可实现路径重建。