GESP 七级 · GESP 七级样题（C++ 组） 第 8 题

动态规划将一个问题分解为一系列子问题后来求解。下面关于子问题的描述正确的是（ ）。

拿到题先别急着背定义，脑子里过一遍DP和分治、贪心的区别：分治是把大问题拆成互不干扰的小块，DP拆出来的小块是互相‘打架’的，这就是重叠子问题。

很多学生死记‘最优子结构’，看到D选项说‘最优解可由子问题非最优解推导’就慌了，其实D错在偷换概念，DP的最优解只能由子问题的最优解拼出来；B选项利用‘都是分解’的模糊直觉，让人误以为DP和分治一样，忽略了分治子问题互斥、DP子问题重叠的本质；C选项太绝对，DP当然有最优子结构，只是题目问的是‘不具有’，直接排除。

【考点】动态规划｜重叠子问题｜最优子结构

动态规划的核心特征就是两点：一是子问题重叠，二是具备最优子结构。命题人把‘重叠子问题’作为正确选项，就是专门卡住那些把DP和分治、贪心混为一谈的学生。

逐项分析： A选项‘具有重叠子问题的性质’完全正确。DP和分治最大的区别就在这儿：分治（比如归并排序）把大问题拆成互不干扰的小块，各干各的；DP拆出来的子问题却是互相‘打架’的，同一个子问题会被反复计算，这才需要记忆化或填表优化。 B选项‘和分治法的子问题类似’错得离谱。分治的子问题是互斥的，DP的子问题是重叠的，这是本质区别，不能因为都叫‘分解’就混为一谈。 C选项‘不具有最优子结构的性质’更是自相矛盾。DP没有最优子结构就没法递推，这是DP成立的基石，C直接把基石拆了。 D选项‘问题的最优解可以由部分子问题的非最优解推导出来’偷换了概念。DP的最优解只能由子问题的最优解拼出来，非最优解怎么拼也拼不出全局最优，D直接违背最优子结构原则。

【思考心法】做这类概念题，先问自己：这道题是不是在考DP的独有特征？是不是在拿一个相似但不同的算法做干扰？DP的独有特征就是‘重叠子问题’，其他算法要么互斥（分治），要么无重叠（贪心）。反命题思维：若把题干改成‘动态规划子问题不具有重叠性’，答案立刻反转，说明命题人刻意用‘重叠’作为锚点。

【避坑提醒】三个错误选项设计极其阴险。B利用‘都是分解子问题’的模糊直觉偷换概念；C用绝对化表述‘不具有’制造认知盲区，学生只记结论不深究就会掉坑；D把‘最优解’偷换成‘部分子问题非最优解’，属于语义陷阱，谁没背过‘最优子结构’定义谁就中招。记住：DP的难点不在于公式，而在于识别‘重叠’这一前提条件。