Problem B: [CSP-S1][选择] 动态规划2

1. 动态规划中“记忆化搜索”的作用是？
A. 减少空间复杂度
B. 避免重复计算子问题
C. 优化状态转移方程
D. 提高算法可读性

2. 序列 [3 4 -1 0 6 2 3] 的最长上升子序列长度是？

A. 4
B. 5
C. 6
D. 7

3. 完全背包问题：背包容量为 10，物品重量 [2 3 4]，价值 [3 4 5]，物品无限，最大价值是？

A. 15
B. 16
C. 17
D. 18

4. 动态规划求解编辑距离（Levenshtein距离）时，状态 dp[i][j] 表示？

A. 字符串 A 的前 i 个字符和 B 的前 j 个字符的匹配数
B. 字符串 A 的前 i 个字符和 B 的前 j 个字符的编辑距离
C. 字符串 A 的第 i 个字符和 B 的第 j 个字符的差异
D. 字符串 A 和 B 的公共子序列长度

5. 以下问题中，适合用动态规划解决的是？

A. 图的深度优先搜索
B. 哈夫曼编码
C. 最大子数组和
D. 快速排序

6. 动态规划的时间复杂度通常取决于？

A. 状态数量和状态转移复杂度
B. 问题规模
C. 空间复杂度
D. 递归深度

7. 序列 [2 -1 4 -3 5 -2] 的最大子数组和是？

A. 7
B. 8
C. 9
D. 10

8. 用动态规划求解斐波那契数列时，若用数组存储中间结果，空间复杂度是？

A. O(1)
B. O(n)
C. O(\log n)
D. O(n^2)

9. 状态压缩动态规划常用于？

A. 减少时间复杂度
B. 优化空间复杂度
C. 处理高维状态
D. 避免递归

10. 动态规划求解最长公共子序列（LCS），序列 "ABCBDAB" 和 "BDCAB" 的 LCS 长度是？

A. 3
B. 4
C. 5
D. 6