NOIP 普及组初赛 · NOIP 2012 普及组初赛试题 第 15 题

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

题干那句“分成两个或更多相同类似的子问题”就是分治算法最核心的“分解”步骤，直接锁定 C 选项即可。

最容易把分治和动态规划搞混。动态规划虽然也分解，但它的子问题往往重叠，需要记忆化；而分治强调子问题互不重叠，最后还要“合并”结果。另外，贪心是每一步局部最优，根本不分解；搜索是暴力遍历。如果只盯着“分解”二字，忽略“合并”和“子问题独立性”，就会误选动态规划。

考点与概念人话版

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

这就是分治（Divide and Conquer）的标准定义：

• 分解（Divide）：把大问题拆成若干规模更小、结构相同的小问题；
• 解决（Conquer）：递归求解这些小问题；
• 合并（Combine）：把子问题的解拼起来得到原问题的解。

命题人怎么挖坑

NOIP 初赛爱考概念辨析，分治和动态规划是最大的一对“双胞胎”：

• 两者都会“分解”；
• 但分治的子问题互不重叠，合并是必须的；
• 动态规划的子问题大量重叠，靠“记忆化/表格”避免重复计算。

命题人常把“分解”“子问题”“最优解”这些词混在一起，让你选动态规划；或者把“合并”“递归”“相同结构”这些词凑成贪心/搜索的干扰项。本题题干明确说了“原问题的解就是子问题解的并”，这就是在强调“合并”这一步，直接指向分治。