GESP 六级 · GESP 202412 C++ 六级 第 14 题

以下关于动态规划的描述，（ ）是正确的。

贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。

贪心算法需要严格证明正确性。典型错误：局部最优不等于全局最优。例如0-1背包问题就不能用贪心。

【考点】动态规划性质｜重叠子问题｜贪心算法

动态规划的核心在于“最优子结构”与“无后效性”——前者指全局最优解可由局部最优解组合而成，后者指一旦状态确定，后续决策不会影响已决策部分的性质。若问题不满足这两点（如存在状态回溯依赖），DP 就无法保证正确性。选项 B 直接命中定义，而 A 错在“没有重叠子问题”（DP 恰恰需要重叠）、C 错在“通常递归”（实际多用自底向上迭代）、D 错在贪心与重叠子问题的关系（贪心可处理重叠子问题）。

A 项是命题人故意颠倒：DP 的标志性场景就是“重叠子问题 + 最优子结构”，若没有重叠，直接分治或贪心即可，DP 失去存在意义；C 项偷换实现方式——教材常说的递归记忆化只是 DP 的两种写法之一，考试常考自底向上的空间优化，说“通常递归”属误导；D 项把“贪心”与“重叠子问题”强行对立，贪心算法完全可以处理重叠子问题（如 Dijkstra 路径问题），这里属于语义陷阱。

若改问“非 DP 算法”则 A 成立；若选项 C 改为“通常迭代”则正确；D 若强调“贪心不依赖重叠子问题”则成立。刷到此类题先问：命题人想考我什么概念的本质？