一、单项选择题（每题2分，共20分）

1、本讲区间DP“两端扩展”思想，循环的外层优先遍历的变量是？（） {{ select(1) }}

• 分割点k
• 区间长度 len
• 区间起点 i
• 区间终点 j

2、最长回文子串中dp[i][j]存储的数据类型与含义是？（） {{ select(2) }}

• 整数，区间最长回文子串长度
• 布尔，判断子串[i,j]是否是回文
• 整数，最少添加字符数量
• 布尔，判断子序列是否回文

3、关于子串与子序列描述正确的是？（） {{ select(3) }}

• 子串字符可以不连续；子序列字符必须连续
• 子串字符必须连续；子序列字符可以不连续
• 两者都必须字符连续
• 两者都可以字符不连续

4、最长回文子序列，两端字符s[i]==s[j]，状态转移正确的是？（） {{ select(4) }}

• dp[i][j] = dp[i+1][j-1] + 2
• dp[i][j] = dp[i+1][j-1]
• dp[i][j] = max(dp[i+1][j],dp[i][j-1])
• dp[i][j] = min(dp[i+1][j]+1,dp[i][j-1]+1)

5、最长回文子序列，两端字符不相等，状态转移为？（） {{ select(5) }}

• dp[i][j]=dp[i+1][j-1]+2
• dp[i][j]=dp[i+1][j-1]
• dp[i][j]=max(dp[i+1][j], dp[i][j-1])
• dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1)

6、最少添加字符把字符串变为回文，两端字符相等时转移方程？（） {{ select(6) }}

• dp[i][j]=dp[i+1][j-1]
• dp[i][j]=dp[i+1][j-1]+2
• dp[i][j]=max(dp[i+1][j],dp[i][j-1])
• dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1)

7、最少添加字符变回文，两端字符不等，转移正确的是？（） {{ select(7) }}

• dp[i][j]=dp[i+1][j‑1]
• dp[i][j]=dp[i+1][j‑1]+2
• dp[i][j]=max(dp[i+1][j],dp[i][j‑1])
• dp[i][j]=min(dp[i+1][j]+1,dp[i][j‑1]+1)

8、GBE合法括号最少添加括号问题，除两端扩展转移外，还需要做什么？（） {{ select(8) }}

• 枚举分割点k，合并两个子区间取min
• 直接输出dp[i+1][j‑1]
• 只做max取最大值
• 不需要任何额外操作

9、GBE括号问题，len=1单个括号时，dp[i][i]初始化值为？（） {{ select(9) }}

• 0
• 1
• 2
• len

10、最长回文子序列最终答案从哪里获取？（） {{ select(10) }}

• 遍历所有dp[i][j]取最大布尔值
• dp[0][l‑1]
• dp数组所有元素求和
• dp[1][1]

二、判断题（每题2分，共10分）

11、区间DP两端扩展模型，要先算大区间，再算小区间。（） {{ select(11) }}

• 正确
• 错误

12、最长回文子串dp[i][j]为true，条件：两端字符相等并且中间子串是回文。（） {{ select(12) }}

• 正确
• 错误

13、最长回文子串的dp数组存储的是回文子序列的长度。（） {{ select(13) }}

• 正确
• 错误

14、GBE合法括号问题，只写两端扩展转移就可以得到全部正确结果。（） {{ select(14) }}

• 正确
• 错误

15、len=1的区间，回文修改（加字符）dp[i][i]=0，单个字符本身是回文。（） {{ select(15) }}

• 正确
• 错误