[题目描述]

{{ 动态规划解决 LCS 问题的核心思想是： }} {{ select(1) }}

• [选项1] 暴力枚举所有可能序列
• [选项2] 递归求解不存储中间结果
• [选项3] 利用子问题重叠性，存储中间结果
• [选项4] 随机猜测最优解

---

[题目描述]

{{ 定义二维数组dp[m+1][n+1]存储 LCS 长度时，dp[i][j]表示： }} {{ select(2) }}

• [选项1] 前 i 个和前 j 个字符的 LCS 长度（下标从 0 开始）
• [选项2] 前 i 个和前 j 个字符的 LCS 长度（下标从 1 开始）
• [选项3] 第 i 个和第 j 个字符是否相等
• [选项4] 最长公共子串的长度

---

[题目描述]

{{ 以下哪段代码正确实现了 LCS 的状态转移方程？ }} {{ select(3) }}

• [选项1]

if (s1[i-1] == s2[j-1])  
    dp[i][j] = dp[i-1][j-1] + 1;  
else  
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

• [选项2]

if (s1[i] == s2[j])  
    dp[i][j] = dp[i-1][j-1] + 1;  
else  
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

• [选项3]

if (s1[i-1] == s2[j-1])  
    dp[i][j] = dp[i-1][j] + 1;  
else  
    dp[i][j] = dp[i-1][j-1];

• [选项4]

if (s1[i] == s2[j])  
    dp[i][j] = dp[i][j-1] + 1;  
else  
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

---

[题目描述]

{{ 计算字符串 "ABCBDAB" 和 "BDCABA" 的 LCS 长度，结果是： }} {{ select(4) }}

• [选项1] 3
• [选项2] 4
• [选项3] 5
• [选项4] 6

---

[题目描述]

{{ 若 LCS 问题中两个字符串长度分别为 m 和 n，动态规划解法的时间复杂度是： }} {{ select(5) }}

• [选项1] O(m+n)
• [选项2] O(m*n)
• [选项3] O(2^(m+n))
• [选项4] O(m^n)

---

[题目描述]

{{ 递归求解 LCS 时未使用记忆化会导致： }} {{ select(6) }}

• [选项1] 结果错误
• [选项2] 大量重复计算
• [选项3] 空间复杂度降低
• [选项4] 时间复杂度变为多项式级

---

[题目描述]

{{ 以下哪种数据结构最适合存储 LCS 中间结果？ }} {{ select(7) }}

• [选项1] 一维数组
• [选项2] 二维数组
• [选项3] 栈
• [选项4] 哈希表

---

[题目描述]

{{ 动态规划求解 LCS 时，初始化dp[0][j]和dp[i][0]的值为： }} {{ select(8) }}

• [选项1] 随机值
• [选项2] 1
• [选项3] 0
• [选项4] 字符串长度

---

[题目描述]

{{ 判断：LCS 问题中，子序列必须连续出现。 }} {{ select(9) }}

• [选项1] A正确
• [选项2] B错误

---

[题目描述]

{{ 判断：动态规划解法一定比递归解法效率高。 }} {{ select(10) }}

• [选项1] A正确
• [选项2] B错误

---

[题目描述]

{{ 判断：若两个字符串没有公共字符，LCS 长度为 0。 }} {{ select(11) }}

• [选项1] A正确
• [选项2] B错误

---

[题目描述]

{{ 判断：计算 LCS 时，dp[m][n]即为最终结果，其中 m 和 n 是字符串长度。 }} {{ select(12) }}

• [选项1] A正确
• [选项2] B错误