1. 关于动态规划算法特性的描述，正确的是（ ）。

{{ select(1) }}

• 贪心选择性质
• 最优子结构和重叠子问题
• 分而治之
• 局部最优

2. 下列关于动态规划与分治算法的说法，正确的是（ ）。

{{ select(2) }}

• 两者都要求子问题相互独立
• 动态规划适用于子问题重叠的情况，分治适用于子问题不重叠的情况
• 两者都是将大问题分解为子问题，但动态规划一定使用递归
• 分治算法一定比动态规划更优

3. 下列关于 0-1 背包问题的动态规划解法，说法正确的是（ ）。

{{ select(3) }}

• 状态转移方程为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])，其中 i 表示物品编号，j 表示容量
• 一维数组实现时，内层循环应从小到大遍历容量
• 完全背包问题可以用相同的一维数组解法，但内层循环同样需要从大到小
• 0-1 背包问题不能使用贪心算法求解，但动态规划一定能找到最优解

4. 关于动态规划的“记忆化搜索”实现，下列说法正确的是（ ）。

{{ select(4) }}

• 它是自顶向下的
• 它是自底向上的
• 它不使用递归
• 它比递推实现占用内存更少

5. 动态规划的核心思想是（ ）。

{{ select(5) }}

• 将问题分解为相互重叠的子问题
• 每一步都取当前最优解
• 将问题分解为相互独立的子问题
• 随机选择解

6. 给定 n 个物品和一个最大承重为 W 的背包，每个物品有重量 w[i] 和价值 v[i]，每件物品只能选或不选。该问题的性质是（ ）。

{{ select(6) }}

• 完全背包问题
• 0-1 背包问题
• 多重背包问题
• 分组背包问题

7. 下列关于动态规划的说法，错误的是（ ）。

{{ select(7) }}

• 动态规划需要明确状态和转移方程
• 动态规划一定优于贪心算法
• 动态规划适合求解最优化问题
• 动态规划可以避免重复计算

8. 在动态规划问题中，定义状态时，应保证状态满足（ ）。

{{ select(8) }}

• 无后效性
• 最优化原理
• 重叠子问题
• 以上都是

9. 动态规划求解背包问题时，状态转移方程 dp[j] = max(dp[j], dp[j - w[i]] + v[i]) 适用于（ ）。

{{ select(9) }}

• 0-1 背包的一维数组实现
• 完全背包的一维数组实现
• 多重背包
• 分组背包

10. 下列哪些是动态规划的特点？（ ）

{{ multiselect(10) }}

• 最优子结构
• 贪心选择
• 重叠子问题
• 自底向上或自顶向下求解

11. 下列哪些算法可以用动态规划求解？（ ）

{{ multiselect(11) }}

• 背包问题
• 最长公共子序列
• 最短路径（Dijkstra 算法）
• 斐波那契数列

12. 下列哪些问题是典型的动态规划问题？（ ）

{{ multiselect(12) }}

• 爬楼梯问题
• 最长上升子序列
• 最短路径（无权图）
• 0-1 背包问题

13. 关于动态规划的状态转移方程，下列哪些说法是正确的？（ ）

{{ multiselect(13) }}

• 描述了问题状态之间的关系
• 是动态规划的核心
• 通常需要边界条件配合
• 必须使用递推公式

14. 关于动态规划，下列说法正确的有（ ）。

{{ multiselect(14) }}

• 动态规划适用于有重叠子问题的问题
• 动态规划适用于有最优子结构的问题
• 动态规划可以用于多阶段决策问题
• 动态规划一定比贪心算法更优

15. 下面代码采用动态规划求解零钱兑换：给定若干硬币面值 coins，目标金额 amt，每种硬币可重复选取；若无法凑出目标金额，返回 -1。（ ）

{{ select(15) }}

• 正确
• 错误

16. 动态规划问题一定可以使用贪心算法求解。（ ）

{{ select(16) }}

• 正确
• 错误

17. 动态规划问题中，状态转移方程一旦确定，算法的实现方式就完全确定了。（ ）

{{ select(17) }}

• 正确
• 错误

18. 动态规划算法只适用于一维数组类型的问题。（ ）

{{ select(18) }}

• 正确
• 错误

19. 动态规划的核心思想是将问题分解为相互独立且不重叠的子问题。（ ）

{{ select(19) }}

• 正确
• 错误