GESP 七级 · GESP 202412 C++ 七级 第 10 题

以下关于动态规划的说法中，错误的是（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】动态规划｜递归与迭代｜时间复杂度

🎯 考纲定位 本题考查 GESP 七级"算法设计"模块中动态规划的核心概念，卡住的是考生对 DP 实现策略的本质理解——很多学生只背"拆子问题"口诀，却对递推/递归的时间开销差异毫无概念。

🧠 解题思维 做 DP 概念题先想实现分类：自上而下记忆化递归 vs 自底向上填表迭代。理论时间复杂度由状态转移方程决定，但实际运行时间还受函数调用栈、重复访问等常数因子影响。选项 D 用"总是不低于"这种绝对化表述，是典型的命题陷阱——迭代通常因无递归开销而更快，而非更慢，因此 D 必错。

🪤 陷阱拆解 A 正确：DP 就是把原问题拆成重叠子问题求解；B 正确：递推公式是 DP 的灵魂；C 正确：两类实现都能完成 DP；D 错误：命题人用"总是不低于"偷换概念，把"时间复杂度"和"运行时间"混为一谈。若你只背"DP 要填表"而不理解递归有栈开销，就会误选 D。

🔄 反命题思维 若把 D 改成"迭代实现动态规划方法的空间复杂度总是不低于递归实现"，答案就会变——递归只需保存路径，迭代需要保存整个状态表。刷到 DP 概念题时先问自己：命题人到底在考"理论复杂度"还是"实际开销"？