GESP 六级 · GESP 202606 C++ 六级 第 25 题

动态规划问题通常要求具有最优子结构，并且常常存在重叠子问题。

动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。

DP 的难点在于状态定义。定义太大会超时，定义太小会漏掉最优解。注意初始化和边界条件。

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

本题考查《GESP 六级考试大纲》“算法与数据结构”模块中的动态规划基础概念。命题人意图检验考生是否真正理解 DP 的本质——它不是单纯套用公式，而是对“最优子结构”与“重叠子问题”这两个核心属性的认知。这是六级区别于五级的分水岭，命题人卡住的是“概念辨析”而非“公式套用”。

解题时先识别题干是否为“定义判断型”——动态规划的经典定义确实包含这两点：最优子结构指全局最优解可由子问题最优解组合而成，重叠子问题指相同子问题被重复计算，这正是引入记忆化或 DP 表的根本原因。这类题通法就是“对照课本定义，看陈述是否完整”。注意“通常”二字，意味着允许特例存在，但核心定义必须匹配。

三个典型陷阱：一是忽略“通常”二字，误以为 DP 必须永远满足重叠子问题（其实简单递归 + 记忆化也可归为 DP，只是重叠性不强）；二是混淆“最优子结构”与“最优子问题”（前者是性质，后者是名词）；三是过度纠结反例，忘记命题人考察的是“常规情况”。最阴险的是“通常”——若你只背结论，看到“总是”就选错，看到“通常”就选对，却不知命题人故意用模糊词卡住机械记忆者。此外，若把“重叠子问题”换成“无重叠子问题”，答案必错，因为 DP 的核心就是利用重叠性。

换个条件：若题干把“通常”改成“总是”，答案立刻变错，因为存在无重叠子问题的 DP（如简单递归+记忆化）；若改成“一般不要求”，则违背 DP 定义。刷到此类定义题，先自问“命题人想考我什么”，再对照课本原文，别被“绝对化表述”带跑。也可设想：若换成“动态规划必须用贪心策略”，答案更是错得离谱。