16 算法

本题考查算法设计技术的适用场景。N 皇后问题是一个经典的约束满足问题，逐行摆放皇后，每一行的摆放都要满足“不同列、不同对角线”的约束；一旦当前行的某个位置导致后面无解，就退回来换一个位置——这正是解空间树上的深度优先搜索 + 剪枝回退，即回溯法的标准工作方式。

逐个看错误选项：A 分治法要求问题能分解成若干相互独立、与原问题形式相同的子问题，而皇后的摆放位置之间互相约束（任何两行都冲突），无法划分成独立子问题，分治不适用。B 动态规划法适合具有最优子结构和重叠子问题的优化问题，而八皇后只要求找出可行解、没有“最优”可言，不存在最优子结构。C 贪心法每步取局部最优且不回溯，但皇后摆放一步放错必须退回重放，贪心的“不回头”恰好失效。

记住这个判据组合：约束满足 + 系统搜索 + 要回退 = 回溯法。同类的还有迷宫求解、图着色、子集和等。

本题考查分治法的实际运用。分治找假币的过程是：先把硬币对等分成两堆，称重比较一次，假币一定在较轻的那一堆；然后对轻的那堆继续对半分、继续称。每称一次，候选范围减半。

具体推一遍：16 枚分成 2 堆（各 8 枚）称第 1 次，锁定轻的 8 枚；8 枚分成 2 堆（各 4 枚）称第 2 次，锁定 4 枚；4 枚分成 2 堆（各 2 枚）称第 3 次，锁定 2 枚；最后 2 枚再称第 4 次，轻的即假币。共 4 次。

错误选项的迷惑点：A 的 3 次只够从 8 枚中找假币（2³=8），覆盖不了 16 枚（需要 2⁴=16）；C 的 5 次、D 的 6 次是“每次只拿出一枚来比较”这种低效做法的次数，没有体现分治“对半砍”的威力。一般地，n 枚硬币用对半分治需要 ⌈log₂n⌉ 次比较。

本题考查分治算法的基本概念，属于概念辨析题，四个说法只有一个是严谨的。

A 正确：分治的标准流程就是划分→递归求解→合并三步，这是教材定义的原话。

B 错在“一定”：分治往往用递归实现，但并非必须。比如二分查找既可递归也可用 while 循环迭代实现，只要逻辑上“分而治之”就是分治思想，实现手段不限。

C 错在“规模相等”的绝对化：分治最理想的情况是划分为 k 个规模相等的子问题，但很多时候问题无法均匀划分（例如快速排序的划分结果取决于基准元素，可能一边大一边小）。

D 错在把代价关系说反了、说死了：划分代价和合并代价依问题而定——归并排序的主要代价在合并上，快速排序的主要代价却在划分上，两者没有固定的大小关系。

这类概念题的关键是警惕“一定”“必须”“都是”这类绝对化措辞，选项里出现基本可以判定为错。

本题考查算法设计策略的识别。题干描述的其实就是快速选择（Quickselect）算法：其中的“划分操作”与快速排序的划分完全一样——确定某元素 r 的最终位置后，r 之前的元素都小于 r，之后的都大于 r，于是顺便知道了 r 是第几小的数。

为什么是分治而不是别的：算法把原问题分解成一个规模更小的同类子问题（前半部分或后半部分），递归求解，直到命中第 i 小——这是标准的“划分 + 递归”结构。与快速排序唯一的区别是它每次只递归一边，另一边直接丢弃，因此平均时间复杂度是 O(n) 而不是 O(nlgn)。

逐个排除：B 动态规划要保存重叠子问题的解，这里每次只处理一个子问题、没有重叠；C 贪心是“每步做局部最优选择”，而这里的划分只是为了缩小范围，不存在“最优选择”的概念；D 回溯要有“走不通退回来换路”的过程，这里方向明确（i<k 往左，i>k 往右），从不回头。

识别分治的关键词：划分（partition）、递归、子问题与原问题同构。

本题考查分治算法的复杂度分析，必须写出递推式。按题干描述：把数组对半分成两半，最大子段有三种可能——完全在左半段、完全在右半段、跨越中间。左右两种情况递归求解；跨越中间的情况可以从中点向两侧各做一次线性扫描求出，代价 O(n)。

于是递推式为 T(n) = 2T(n/2) + O(n)。用主定理（n^log₂2=n，与 f(n)=n 同阶，属于第二种情况）得 T(n) = O(nlgn)；也可以画递归树：共 lgn 层，每层合并代价合计 O(n)，总代价 n·lgn。

错误选项分析：B 的 O(n²) 是“枚举所有子数组起止位置”的朴素做法，不是题干描述的分治；C、D 把分治的“每层 O(n)”误当成“每次划分 O(n²) 或 O(n³)”，量级明显偏高。另外要知道补充知识：此问题用动态规划（Kadane 算法，一重循环）可以做到 O(n)，比分治更快，但题干问的就是这套分治流程的复杂度。

本题考查各算法设计策略的目标定位，一句话就能区分。

C 正确：动态规划通常用于求解具有某种最优性质的问题——这类问题可能有很多可行解，每个解对应一个值，我们希望找到具有最优值（最大或最小）的那个解。矩阵链乘求最少乘法次数、背包求最大价值，全是以“最优”为目标的典型。

逐个看错误选项：A 回溯方法的目标是系统地搜索解空间，找出问题的所有解或任一可行解，不追求“最优”（虽然配合限界函数也能求最优，但其本职是搜索）；B 分治法的目标是把问题各击破求出原问题的解，不特指最优解，比如归并排序只求排好序；D 递推只是按递推关系逐项计算的计算手段（如斐波那契数列），本身没有最优解的概念。

这题是“策略识别”的最基础形态：看到“最优解”三个字，优先在动态规划和贪心里选；本题四个选项里只有动态规划是以最优解为目标的完整方法论。

本题考查矩阵链乘的动态规划求解，p=(p0,p1,p2,p3,p4)=(20,5,35,4,25)。A(m×n)×B(n×p) 的标量乘法次数是 m·n·p，把每个选项的加括号方式逐一代入计算即可。

A：((M1×M2)×M3)×M4 = 20×5×35 + 20×35×4 + 20×4×25 = 3500+2800+2000 = 8300。B：(M1×M2)×(M3×M4) = 3500 + (35×4×25=3500) + 20×35×25 = 24500。C：先算 M2×M3 = 5×35×4 = 700（得 5×4），再 M1×(M2M3) = 20×5×4 = 400（得 20×4），最后 ×M4 = 20×4×25 = 2000，合计 700+400+2000 = 3100。D：M3×M4 = 3500（得 35×25），M2×(M3M4) = 5×35×25 = 4375（得 5×25），M1×(…) = 20×5×25 = 2500，合计 10375。

3100 最小，选 C。规律很直观：让“小维数”的矩阵先相乘，避免产生大矩阵再做昂贵的乘法。M2×M3 的结果只有 5×4，非常“瘦”，后续乘法都便宜。考试时把四个选项都加起来是最稳妥的暴力解法，规模小时代价很低。

本题考查背包问题的两种形态：0-1 背包用动态规划，部分背包用贪心，是“同一实例、两种策略”的对照题。

（62）按递归式自底向上填表：c[i,j] 的含义是“只考虑前 i 个物品、容量为 j 时的最大价值”。逐行递推（行=物品，列=容量0..10）：物品1(2,6)后为 0,0,6,6,6,6,6,6,6,6,6；物品2(2,3)后为 0,0,6,6,9,9,9,9,9,9,9；物品3(6,5)后为 0,0,6,6,9,9,9,9,11,11,14；物品4(5,4)后为 0,0,6,6,9,9,9,10,11,13,14；物品5(4,6)后为 0,0,6,6,9,9,12,12,15,15,15。故 c(5,10)=15，选 C（选物品1、2、5，重2+2+4=8，价值6+3+6=15）。（63）自底向上实现是“物品数 × 容量”两重循环，时间复杂度 Θ(nW)，选 A。

（64）部分背包按单位重量价值排序：v/w 分别为 3、1.5、5/6≈0.83、0.8、1.5。贪心装入：物品1（2kg，价值6）→ 物品2（2kg，价值3）→ 物品5（4kg，价值6），已装 8kg 价值 15，剩 2kg；下一个是物品3（0.83），只能装 2/6=1/3，得 5×1/3≈1.67。总价值 15+1.67=16.67，选 D。（65）归并排序 O(nlgn) + 依次装包 O(n)，整体 O(nlgn)，选 B。

错误的组合各有对应误区：15 是 0-1 背包的答案，搬到部分背包就漏了“可以拆分”；O(nW) 是 0-1 背包动态规划的复杂度，与部分背包的排序法无关；O(n²)、O(nlgnW) 都是干扰项。

本题考查矩阵链乘动态规划算法的复杂度与实例计算。

（64）自底向上求 m[i,j] 需要三重循环：最外层是矩阵链长度 l（从 1 到 n），第二层是子链起点 i（从 1 到 n-l+1），最内层是分割点 k（从 i 到 j-1），每层最多 n 次迭代，故时间复杂度 O(n³)，选 C。A 的 O(n²) 是只算了两重下标循环、漏掉了 min 中枚举 k 的那一重，是最典型的错误。

（65）维度序列 2、6、3、10、3 意味着 M1(2×6)、M2(6×3)、M3(3×10)、M4(10×3)，即 p=(2,6,3,10,3)。按递归式填表：m[1,2]=2×6×3=36；m[2,3]=6×3×10=180；m[3,4]=3×10×3=90；m[1,3]=min(m[1,1]+m[2,3]+2×3×10, m[1,2]+m[3,3]+2×6×10)=min(180+60, 36+120)=min(240,156)=156；m[2,4]=min(m[2,2]+m[3,4]+6×10×3, m[2,3]+m[4,4]+6×3×3)=min(90+180, 180+54)=min(270,234)=234；m[1,4]=min(m[1,1]+m[2,4]+2×6×3, m[1,2]+m[3,4]+2×3×3, m[1,3]+m[4,4]+2×10×3)=min(234+36, 36+90+18, 156+60)=min(270,144,216)=144，选 B。对应的最优加括号方式为 ((M1×M2)×(M3×M4))。

错误选项里 156、234 恰好是中间子问题的值（m[1,3]、m[2,4]），用于迷惑只算了一半的人；180、360 则是选错分割点后的结果。

本题考查装配线调度问题，是动态规划的教科书案例（出自《算法导论》）。

（62）题干已点明两条判据：最优子结构（经过第 j 个工位的最短时间由第 j-1 个工位的最短时间推出）+ 重复子问题（f1,j 和 f2,j 的计算都要用到 f1,j-1 和 f2,j-1）。两个条件齐备，选动态规划。贪心为什么不行：贪心只看当前哪个工位快，但不考虑迁移代价，可能错过“现在慢一点、后面换线更省”的路线。

（63）迭代求解就是一重 j 从 1 到 n 的循环，每步做常数次比较，时间复杂度 Θ(n)，选 B。

（64）（65）按递归式递推：f1,1=e1+a11=3+4=7，f2,1=e2+a21=2+7=9。f1,2=min(f1,1+0+9, f2,1+2+9)=min(16,20)=16（来自线1）；f2,2=min(f2,1+0+5, f1,1+1+5)=min(14,13)=13（来自线1，经 S11→S22）。f1,3=min(f1,2+0+3, f2,2+2+3)=min(19,18)=18（来自线2，经 S22→S13）；f2,3=min(f2,2+0+6, f1,2+3+6)=min(19,25)=19。最后 fmin=min(f1,3+x1, f2,3+x2)=min(18+3, 19+3)=21，选 A。从后往前回推：fmin 来自线1（经 S13），S13 的最优前驱是 S22，S22 的最优前驱是 S11，故路线为 S11→S22→S13，选 B。中间值 16、19、19、22 都是填表过程中出现过的数，是典型的干扰项。

本题考查最长公共子序列（LCS）两种解法的复杂度对比，重点是把蛮力法的指数级算清楚。

（62）长度为 n 的序列 X 共有 2ⁿ 个子序列（每个位置选或不选）。蛮力法对 X 的每一个子序列都要判断“是否为 Y 的子序列”，这一步需要 O(n) 的时间（两个指针各扫一遍）。所以总时间复杂度为 O(n·2ⁿ)，选 D。这是典型的指数级爆炸：n=20 时已经是千万级的子序列数。

（63）动态规划的递归式按 (i,j) 定义 C[i,j]：若 x_i=y_j，则 C[i,j]=C[i-1,j-1]+1；否则 C[i,j]=max{C[i,j-1], C[i-1,j]}。自底向上实现就是对 i、j 的两重循环，表中共 n² 个格子、每格 O(1) 时间，故时间复杂度 O(n²)，选 A。

错误选项的定位：O(n²lgn)、O(n³) 是高估——递归式里既没有排序也没有再套一重循环；把 O(n2ⁿ) 填到（63）则是把蛮力法的代价错安到动态规划头上。这道题的对比正是“为什么动态规划值得学”：从指数级降到多项式级。

本题考查矩阵链乘的完整分析链：策略识别→时间复杂度→空间复杂度→实例求解。

（62）题干给出最优子结构且采用自底向上方法求解，就是动态规划的标准姿势，选 B。（63）求解时要填一个 n×n 的表 m[i,j]，每个格子要在 k 上枚举一遍取 min，是三重循环，时间复杂度 O(n³)。（64）需要一个二维数组 m 保存所有子问题的解（另加一个记录分割点 k 的数组也是 O(n²)），空间复杂度 O(n²)——注意（63）（64）的选项组合是设计好的，时间 O(n³)、空间 O(n²) 别填反。

（65）五个矩阵的维度：A1(20×15)、A2(15×4)、A3(4×10)、A4(10×20)、A5(20×25)。逐项验证：D 即 (A1×A2)×((A3×A4)×A5)：A1×A2=20×15×4=1200（得20×4）；A3×A4=4×10×20=800（得4×20）；(A3A4)×A5=4×20×25=2000（得4×25）；最后 20×4×25=2000。合计 1200+800+2000+2000=6000。A：(((A1A2)A3)A4)A5=1200+800+4000+10000=16000；B：A4×A5=5000、A3×(A4A5)=1000、A2×(…)=1500、A1×(…)=7500，合计 15000；C：((A1A2)A3)(A4A5)=1200+800+5000+5000=12000。D 的 6000 最小，选 D。

记忆技巧：让小的“内维”先结合，把 15×4、4×10 这些瘦矩阵的乘积尽早合并成小矩阵，避免 20×25 的大矩阵反复参与乘法。

本题考查旅行商问题（TSP）的贪心近似解法。

（63）算法每次都选择离当前城市最近的未访问城市——“最近”就是当前看起来最好的选择，且选完不回头，这是典型的贪心策略。要认清一个事实：TSP 本身不具备贪心选择性质，这个“最近邻法”得到的往往只是近似最优解，但它仍然是贪心思想的应用。分治没有“选最近”的结构；动态规划解 TSP 需要状态压缩保存子集（题目描述完全不是）；回溯法要穷举所有路径并在失败时退回。

（64）算选择次数：第 1 个目的地是在 n 个候选里挑最近（比较 n 次），第 2 个在 n-1 个里挑（n-1 次），……最后 1 个只剩 1 种选择。总代价 n+(n-1)+…+1 = n(n-1)/2 = Θ(n²)，选 A。

错误选项分析：O(nlgn) 是排序的复杂度，本题并不排序，而是每轮现找最近；O(n) 想当然地认为“n 个城市各选一次”，漏掉了每次选最近要扫描全部候选；O(1) 显然荒谬。另外记住配套结论：TSP 用贪心不能保证最优，这是选择题常考的判断点。

本题考查背包问题两种形态下贪心策略的表现差异，是本节最经典的对照题。

（60）“单位重量价值大的优先装入”——每一步都装当前性价比最高的物品，这就是贪心策略，选 B。

（61）先算单位重量价值：物品1=10、物品2=8、物品3=6、物品4=5、物品5=4（题干已按此排序）。0/1 背包：依次装入物品1（重5，值50）、物品2（重25，值200）、物品3（重30，值180），此时背包重 5+25+30=60；轮到物品4（重45）时 60+45=105 超过 100，整件放不下，物品5（重50）更是放不下。结果价值 430。注意：本题的真实最优解其实是装物品2、3、4（重恰100、值605），但贪心策略的规则决定了它装不进——这正说明0/1 背包用贪心得不到最优解。部分背包：同样先装物品1、2、3 得 430，剩余容量 40；物品4 单位价值 5，装入 40/45=8/9 份，价值 225×8/9=200。总计 430+200=630。部分背包具有贪心选择性质，贪心结果就是最优解。

所以（61）选 C（430 和 630）。A 的 605 是全局最优解的值，用它作答就掉进了“忘了题目限定用贪心策略”的陷阱；B、D 则是把两个数字张冠李戴。这一对数字（贪心0/1=430 < 最优=605 < 部分背包=630）值得记牢，考试反复在它身上做文章。

本题一题双策略：排序环节和安排环节用了两种不同的设计思想，识别清楚是得分关键。

（62）快速排序选一个基准元素把序列分成独立的两部分再分别递归，是标准的分治算法，选 A。（63）安排活动时，每次取出最先开始的活动，依次尝试已有场地、放得下就放、都冲突才新开场地——每步做当前最好的安排、不回头，是贪心策略，选 C。

（64）排序平均 O(nlgn)（最坏 O(n²)）；安排活动要遍历活动序列，对每个活动又要从 P1 开始逐个检查场地的最后一个活动，活动数和场地数都可能达到 n，两重嵌套为 O(n²)。整体取最大量级 O(n²)，选 D。若只答 O(nlgn)（选项C）就是漏算了安排环节的嵌套遍历。

（65）按规则模拟（注意“结束时间=开始时间”不算冲突）：活动1(0,6)→P1；活动2(1,4)与P1冲突→P2；活动3(2,13)→P3；活动4(3,5)→P4；活动5(3,8)→P5；活动6(5,7)与P1冲突（5<6）但5≥4可入P2；活动7(5,9)入P4（5≥5）；活动8(6,10)入P1（6≥6）；活动9(8,11)入P2（8≥7）；活动10(8,12)入P5（8≥8）；活动11(12,14)入P1（12≥10）。最终 P1={1,8,11}、P2={2,6,9}、P3={3}、P4={4,7}、P5={5,10}，共 5 个场地，选 B。

本题考查区间覆盖型的贪心算法，四空一条线：识别策略→算复杂度→模拟实例→判断性质。

（62）“每次选最左未覆盖的房子、在其右侧20米处安装、删掉被覆盖的房子”——每步做当前最优的选择且不回头，是贪心策略，选 C。（63）从左到右只需遍历房子一次：每栋房子要么被当前消防栓覆盖、要么触发安装新消防栓，每个元素最多被处理一次，时间复杂度 O(n)，选 B。注意题目输入本身就是按坐标给出的，不涉及排序，不要误选 O(nlgn)。

（64）模拟：第1个消防栓装在 10+20=30 处，覆盖 [10,50]，盖住 10、20、30、35 四栋；下一个未覆盖是 60，装在 80 处覆盖 [60,100]，盖住 60、80；再下一个是 160，装在 180 处只盖住 160；然后 210 装在 230 处盖住 210；最后 260 装在 280 处覆盖 [260,320]，盖住 260、300。共 5 个消防栓，选 B。

（65）该问题具有贪心选择性质：最左的房子必须被某个消防栓覆盖，而把它放在“最左房子右侧 20 米”处能覆盖最多的后续房子，因此贪心肯定可以求得问题的一个最优解，选 A。错误选项辨析：B“求得所有最优解”是搜索法的特征，贪心只输出一条路径；C、D 说它得不到最优解，与本题情形相悖——要区分“贪心不保证最优”是就一般问题而言，具体问题若可证明贪心选择性质，则贪心就是最优的（如部分背包、Dijkstra、本题）。另外，一个问题可能存在多个不同的最优方案，贪心只能给出其中一个，这是 A 表述为“一个最优解”的用意。

本题考查循环次数的精确计算，重点是外层循环变量的乘法式增长。

外层 i 从 1 开始每次乘 2：i = 1, 2, 4, 8，下一个 16 已经 > 11 退出，所以外层共执行 4 次。内层循环的次数取决于当前 i：i=1 时内层执行 1 次，i=2 时执行 2 次，i=4 时执行 4 次，i=8 时执行 8 次。count++ 在最内层，总执行次数 = 1+2+4+8 = 15 次，选 A。

错误选项的来源：B 的 16 大概是把“最后一次 i=16 不满足条件”也算了半次、或者把 4 轮各算 4 次；C 的 31 = 2⁴+2³+2²+2+1，是误以为 i 会取到 16（16>11 不成立，不会执行）或者错把内层次数当成 2ⁱ；D 的 32 是典型的“差一个幂”错误。规律总结：外层 i*=2 时外层执行 ⌊log₂上限⌋+1 次（以 1 开头），内层若累加至 i，总量约为 2×最终i - 1；做这类题一定要把 i 的取值序列逐个写出来再代入内层，不能凭感觉。

本题考查 0-1 背包问题的解法性质，是“哪些方法能求最优解”系列的标准题。

0-1 背包的形式化描述：目标函数为 max Σv_ix_i，约束为 Σw_ix_i≤W，x_i∈{0,1}。它具有最优子结构：把某件物品从背包拿掉，剩下的应是“n-1 件物品、容量 W-w_j”子问题的最优解。

B 正确：0-1 背包不具有贪心选择性质——按单位重量价值优先装某件物品后，剩余容量可能刚好卡死，使后面价值更高的组合进不来（见 2013 年真题的实例：贪心得 430，真实最优 605）。局部最优不能保证全局最优，故贪心不能保证求得最优解。

其余三项都能保证最优：A 分支限界法在解空间上做广度优先搜索并用限界函数剪枝，能求得最优解；C 回溯法深度优先系统地搜索整个解空间，同样能保证最优；D 动态规划利用最优子结构和重叠子问题递推，是 0-1 背包的标准最优解法（时间 O(nW)）。

同族考点：部分（分数）背包可以贪心求最优（见 2019 下真题）；0-1 背包求最优要用动态规划、回溯或分支限界。

本题考查 Dijkstra 算法的策略本质，几乎是送分题，但要说得清道理。

C 正确：Dijkstra 把顶点分成集合 S（已确定最短路径）和 T（尚未确定）。初始 S 只含源点 v0。每一轮从 T 中挑选当前距离 v0 最近的顶点并入 S——“按路径长度递增次序产生最短路径”就是在每一步做当前看起来最好的选择，这是贪心的工作方式。而且由于边权非负，这个贪心选择性质成立，该贪心方法可以求得问题的最优解。

排除项：A 分治需要把图分解为独立子图递归求解，最短路径问题不具备这种独立结构；B 动态规划要保存重叠子问题的解，Dijkstra 虽然也维护距离数组，但它的核心动作是“每轮选一个当前最近的顶点定案”，而不是按阶段递推（注意区分：有些教材也从 DP 视角解释 Bellman-Ford，但 Dijkstra 的标准定性是贪心）；D 回溯要搜索解空间并回退，Dijkstra 从不回退。

记忆锚点：Dijkstra = 贪心 + 优先队列；Prim 最小生成树、哈夫曼编码同理，都是“每步选当前最优”的家族成员。

本题考查五大策略的特征匹配，每个空对应一组“特征关键词”。

（64）“最优子结构 + 子问题被重复求解（重叠子问题）”——这两个性质正是动态规划的定义性特征。动态规划保存已解决子问题的答案避免重复计算，求解时一般采用自底向上的方法。对比：分治的子问题相互独立，不会重复求解；贪心还需要“贪心选择性质”这一条，题干没给；回溯是搜索解空间，与“重复求解子问题”无关。

（65）“定义问题的解空间 + 深度优先搜索”——这是回溯法的标准定义：解空间树上从根出发深度优先搜索，进入子树发现无解就回退到父节点换分支。与之成对出现的知识：若以广度优先方式搜索解空间，则是分支限界法（本卷 2021 年真题正好反过来考了一次，见下题）。记忆口诀：深搜回溯、广搜限界。

错误选项的干扰逻辑：把“深度优先”错配到分支限界（D），或者把“重叠子问题”错配到分治（A），都是特征记忆不牢的表现。把这张特征表背熟，这一族的题目可以全部秒杀。

本题考查贪心算法的适用边界，正面问“贪心何时保证最优”。

D 正确：部分背包问题中物品可以拆分装入。先按单位重量价值排序，依次装入；轮到装不下的物品时装入其一部分填满背包。由于拆分自由，任何时刻背包里的每一点容量都装着当前剩余物品中单位价值最高者，交换论证可证这就是全局最优——部分背包具有贪心选择性质，贪心保证最优。

逐个看错误选项：A 的 0-1 背包不具有贪心选择性质（物品不可拆，按性价比贪心会卡壳，2013 年实例中贪心 430 < 最优 605），贪心不保证最优，求最优要用动态规划/回溯/分支限界；B 的矩阵链乘要用动态规划求最优加括号方式，贪心“每次先乘最小的”并没有一般保证；C 的最长公共子序列同样靠动态规划（O(n²)）求解，没有可行的贪心策略。

把结论表记全：贪心保证最优的常见问题 = 部分（分数）背包、Dijkstra 单源最短路径、Prim/Kruskal 最小生成树、哈夫曼编码；贪心不保证最优的 = 0-1 背包、TSP。这一正一反两列清单在上午题里反复出现。

本题与 2013 年下半年真题（本章真题 20）成对出现，把特征匹配的两个方向各考一次，足以说明这张“特征表”的考查频率。

（64）“最优子结构 + 重叠子问题”——动态规划的两大特征同时出现。动态规划求解问题的特征正是这两条，求解时自底向上保存子问题解。对比记忆：分治要求子问题独立（不重叠）；贪心要求最优子结构加贪心选择性质，题干没给贪心选择性质，故不选 B；回溯根本不谈最优子结构。

（65）“了解（定义）问题的解空间 + 广度优先搜索”——这是分支限界法：以广度优先（或最小耗费优先）的方式搜索解空间，通常配合限界函数剪枝以求更快找到最优解。与它成对的是回溯法的深度优先。口诀还是那句：深搜回溯、广搜限界。

错误选项辨析：把（65）答成回溯（C）是最常见的失误——回溯与分支限界都“定义解空间、系统搜索”，唯一的区分维度就是搜索顺序：深度优先回溯，广度优先限界。另外注意（64）若在选项里同时出现“动态规划”和“贪心”，判据就看题目是否给出贪心选择性质；只给最优子结构+重叠子问题时，答案是动态规划。