NOIP 普及 2012 第一轮 第 15 题：分治算法的基本思想

题目

（    ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。

选项

• A. 动态规划
• B. 贪心
• C. 分治
• D. 搜索

答案

C

题解

考点定位

本题考「分治法定义」,对应大纲 4.2.1 分治（难度【1】）。

解题过程

「分解为相同子问题 → 解子问题 → 合并」= 分治（divide and conquer）。

选 C。

易错提醒

① 分治：子问题独立；DP：子问题重叠+记录；② 「原问题的解是子问题解的并」暗示合并不复杂（如归并、快速排序）。