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

应用动态规划算法时，识别并存储重叠子问题的解是必须的。

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

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

【考点】动态规划｜重叠子问题｜状态复用

1. 🎯 考纲定位 GESP 六级/七级 动态规划模块。命题人卡死考生对 DP 本质的理解——很多人以为 DP=递归，其实 DP 的核心是“状态复用”，这道题就是专门筛掉只会背“最优子结构”却不懂“重叠子问题”的伪 DP 选手。

2. 🧠 解题思维 看到“动态规划”立刻触发两个关键词：最优子结构 + 重叠子问题。题目陈述的是 DP 的标准定义，存储子问题解正是为了避免重复计算，所以直接选 A。这一类题的通法是：凡题中出现“动态规划”“状态转移”“填表”等字眼，优先想“是否有重叠子问题需要缓存”。

3. 🪤 陷阱拆解 错选 B 的人常混淆 DP 与贪心（贪心不存子问题）或分治（分治不一定重叠）。题目“必须”二字是绝对化表述，若考生没理解 DP 定义，就会误判。更阴险的是很多人把“动态规划”和“记忆化递归”混为一谈，以为只要写了递归就算 DP——其实没存子问题解的递归只是暴力搜索，毫无优化可言。

4. 🔄 反命题思维 若改成“DP 只适用于有重叠子问题的问题”，答案变错，因为 DP 也能处理无重叠子问题（如矩阵链乘）。刷到此类题先问：命题人想考我“定义”还是“应用条件”？