动态规划与分治思想基础

第 1 题（单选）

关于分治算法，下列说法错误的是（）。

{{ select(1) }}

• 分治算法的核心思想是分而治之
• 分治算法可以不使用递归实现
• 分治算法的时间复杂度一定是 O(log N)
• 二分法、快速排序等算法都是典型的分治算法

第 2 题（单选）

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

{{ select(2) }}

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

第 3 题（单选）

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

{{ select(3) }}

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

第 4 题（单选）

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

{{ select(4) }}

• 状态转移方程为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
• 一维数组实现时，内层循环应从小到大遍历容量
• 完全背包问题内层循环同样需要从大到小
• 0-1 背包问题总能用按单位价值排序的贪心策略得到最优解

第 5 题（单选）

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

{{ select(5) }}

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