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

1、关于子段和子序列说法正确的是？（） {{ select(1) }}

• 子段可以不连续，子序列必须连续
• 子段必须连续，子序列可以不连续，保持原有先后顺序
• 子段和子序列都必须连续
• 子段和子序列都可以不连续

2、最大子段和问题中，dp[i]的含义是？（） {{ select(2) }}

• 前i个数字的总和
• 区间1~i的最大子段和
• 以第i个数字作为结尾的最大连续子段和
• 从第1个到第i个的最小子段和

3、最大子段和状态转移方程正确的是？（） {{ select(3) }}

• dp[i]=max(a[i], dp[i‑1]+a[i])
• dp[i]=dp[i‑1]+a[i]
• dp[i]=max(dp[i‑1],a[i])
• dp[i]=dp[i‑1]-a[i]

4、最长上升子序列LIS，dp数组初始化正确的是？（） {{ select(4) }}

• 全部初始化为0
• 全部初始化为‑1
• 全部初始化为1
• 全部初始化为n

5、高楼观望（可见大楼）问题，内层循环j的遍历方向以及遇到a[j]>=a[i]操作是？（） {{ select(5) }}

• j从1到i‑1，continue继续循环
• j从i‑1倒序到1，直接break跳出内层循环
• j从1到i‑1，直接break跳出内层循环
• j从i‑1倒序到1，continue继续循环

6、最长公共子序列LCS，当两个字符串当前字符s1[i]==s2[j]时，状态转移为？（） {{ select(6) }}

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

7、LCS问题字符不相等时，状态转移方程是？（） {{ select(7) }}

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

8、上升点列题目，对点排序规则是？（） {{ select(8) }}

• x从大到小，x相等y从大到小
• x从小到大，x相等y从小到大
• 只按照y从小到大排序
• 随机顺序，不需要排序

9、上升点列中两点l到j之间需要插入的点数量t计算公式为？（） {{ select(9) }}

• t = a[j].x‑a[l].x + a[j].y‑a[l].y‑1
• t = a[j].x + a[l].x + a[j].y + a[l].y
• t = abs(a[j].x‑a[l].x)
• t = abs(a[j].y‑a[l].y)

10、下面哪一个问题属于二维dp（dp为二维数组）？（） {{ select(10) }}

• 最大子段和
• 普通最长上升子序列LIS
• 最长公共子序列LCS
• 高楼观望问题

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

11、最大子段和的dp数组结果，最后直接输出dp[n]就是最终答案。（） {{ select(11) }}

• 正确
• 错误

12、普通LIS（最长上升子序列），状态转移条件是a[j] < a[i]。（） {{ select(12) }}

• 正确
• 错误

13、LCS解题时，把字符串下标改成从1开始，可以防止i‑1、j‑1发生下标越界。（） {{ select(13) }}

• 正确
• 错误

14、高楼观望问题可以直接复制普通LIS代码，不需要修改循环方向。（） {{ select(14) }}

• 正确
• 错误

15、上升点列dp[i][j]代表：以第j个原始点为终点，使用i个新增点时的路径最大点数。（） {{ select(15) }}

• 正确
• 错误