Problem B: [CSP-S1][选择] 动态规划1
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：83
Solved：10
Description
1. 斐波那契数列的第 n 项定义为 F(n) = F(n-1) + F(n-2)，F(1)=1 F(2)=1。求 F(10) 的值是？
A. 55
B. 89
C. 34
D. 144
B. 5
C. 6
D. 7
B. 11
C. 12
D. 13
B. 24000
C. 20000
D. 32000
B. O(n^2)
C. O(n^3)
D. O(n \log n)
C. 图的拓扑排序
D. 编辑距离
B. 10
C. 9
D. 8
B. 4
C. 5
D. 6
B. 必须使用递推形式
C. 必须包含最优子结构
D. 必须包含重叠子问题
B. 树的直径问题
C. 最短路径
D. 最大流问题
A. 55
B. 89
C. 34
D. 144
2. 用动态规划求解最长上升子序列（LIS），序列 [3 1 4 1 5 9 2 6] 的 LIS 长度是？
A. 4B. 5
C. 6
D. 7
3. 0-1背包问题：背包容量为 10，物品重量 [2 3 4 5]，价值 [3 4 5 6]，最大价值是？
A. 10B. 11
C. 12
D. 13
4. 矩阵链乘法：矩阵尺寸 [10 20 30 40] 的最小乘法次数是？
A. 18000B. 24000
C. 20000
D. 32000
5. 动态规划求解最短路径问题（Floyd算法）的时间复杂度是？
A. O(n)B. O(n^2)
C. O(n^3)
D. O(n \log n)
6. 以下问题中，不能用动态规划解决的是？
A. 最长公共子序列（LCS）
B. 旅行商问题（TSP）C. 图的拓扑排序
D. 编辑距离
7. 序列 [1 2 3 4 5] 的连续子数组最大和是？
A. 15B. 10
C. 9
D. 8
8. 用动态规划求解硬币找零问题：硬币面值 [1 2 5]，目标金额 11，最少硬币数是？
A. 3B. 4
C. 5
D. 6
9. 以下关于状态转移方程的描述，正确的是？
A. 必须包含边界条件B. 必须使用递推形式
C. 必须包含最优子结构
D. 必须包含重叠子问题
10. 树形动态规划常用于解决？
A. 图的连通性B. 树的直径问题
C. 最短路径
D. 最大流问题
Sample Input Copy
Sample Output Copy