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

1、区间动态规划中dp[i][j]的含义是？（） {{ select(1) }}

• 前i个元素的最优解
• 区间i到j的最优解
• 从i到j元素的总和
• 第i个到第j个元素的最大数值

2、区间DP循环时，外层最先循环的变量是？（） {{ select(2) }}

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

3、线形合并石子问题，len=1（区间只有一堆石子）时，dp[i][i]应当赋值为？（） {{ select(3) }}

• 极大值
• 0
• 该堆石子数量
• 1

4、合并石子求区间[i,j]石子总和，使用前缀和sum正确写法是？（） {{ select(4) }}

• sum[j] + sum[i‑1]
• sum[j] + sum[i]
• sum[j] - sum[i‑1]
• sum[j] - sum[i]

5、线形合并石子状态转移方程，cost代表区间代价，正确的是？（） {{ select(5) }}

• dp[i][j]=max(dp[i][j], dp[i][k]+dp[k+1][j]+cost)
• dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+cost)
• dp[i][j]=dp[i][k]+dp[k+1][j]
• dp[i][j]=dp[i][k] * dp[k+1][j]

6、环形石子合并解决“环”的手段是？（） {{ select(6) }}

• 直接修改循环起点
• 增加一层循环枚举分割点
• 破环为链，数组复制一份拼接在尾部
• 将dp数组扩大一倍，值不变

7、环形石子合并跑完DP后，最终答案如何获取？（） {{ select(7) }}

• 直接输出dp[1][n]
• 在所有长度为n的区间dp[i][i+n‑1]中取最优
• 输出dp[n][2*n]
• 取dp数组全部元素的平均值

8、抽卡片（消卡片）题目，能够产生得分的区间最小长度为？（） {{ select(8) }}

• 2
• 1
• n
• 3

9、抽卡片问题状态转移公式中a[i]*a[k]*a[j]代表？（） {{ select(9) }}

• 区间石子总重量
• 取出k号卡片获得的分数
• 区间元素求和
• 前缀和结果

10、区间DP求最小值，dp数组未初始化的位置需要赋值？（） {{ select(10) }}

• 极大值INF
• 0
• 极小值
• 1

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

11、区间DP要先计算大区间，再计算小区间。（） {{ select(11) }}

• 正确
• 错误

12、合并石子，每次只能合并相邻的两堆石子。（） {{ select(12) }}

• 正确
• 错误

13、环形石子合并可以直接使用线形石子的答案dp[1][n]作为最终结果。（） {{ select(13) }}

• 正确
• 错误

14、分割点k的作用是把区间[i,j]拆分为[i,k]与[k+1,j]两个子区间。（） {{ select(14) }}

• 正确
• 错误

15、数值较大的区间DP题目，要注意使用long long防止整数溢出。（） {{ select(15) }}

• 正确
• 错误