单选题 适中
#19734

下面程序使用动态规划求两个字符串的最长公共子序列(LCS)长度,横线处应填入的是( )。 # include <algorithm> # include <st…

下面程序使用动态规划求两个字符串的最长公共子序列(LCS)长度,横线处应填入的是( )。

#include <algorithm> 
#include <string> 
#include <vector> 
using namespace std; 

int lcs_len(const string &a, const string &b) { 
  int n = (int)a.size(), m = (int)b.size(); 
  vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); 
  for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= m; j++) 
      if (a[i - 1] == b[j - 1]) 
        dp[i][j] = dp[i - 1][j - 1] + 1; 
    else 
    ________; // 在此处填入选项 
  return dp[n][m]; 
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:C
解析
定义状态 dp[i][j] 表示字符串 a 的前 i 个字符与字符串 b 的前 j 个字符的最长公共子序列长度。初始化二维数组 dp,边界为 0。遍历两个字符串的每一个字符位置,当字符相等时,状态转移来源于左上角加一;当字符不相等时,状态转移来源于上方或左方的最大值,以保持当前最长公共子序列长度的最优性。最终结果由 dp[n][m] 给出,整个过程依据子问题的最优解构造父问题解。