单选题
适中
#19734
下面程序使用动态规划求两个字符串的最长公共子序列(LCS)长度,横线处应填入的是( )。 # include <algorithm> # include <st…
下面程序使用动态规划求两个字符串的最长公共子序列(LCS)长度,横线处应填入的是( )。
答案与解析
正确答案:C
解析
定义状态 dp[i][j] 表示字符串 a 的前 i 个字符与字符串 b 的前 j 个字符的最长公共子序列长度。初始化二维数组 dp,边界为 0。遍历两个字符串的每一个字符位置,当字符相等时,状态转移来源于左上角加一;当字符不相等时,状态转移来源于上方或左方的最大值,以保持当前最长公共子序列长度的最优性。最终结果由 dp[n][m] 给出,整个过程依据子问题的最优解构造父问题解。