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

在动态规划问题中，状态空间相同且没有重复计算的情况下，“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。

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

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

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

🎯 考纲定位 GESP 六级「算法设计与分析」模块。命题人专门卡住那些只背「动态规划要写递推式」却分不清两种实现方式时间开销的考生——他们以为递归写法天然更慢，或者记忆化会引入额外开销。

🧠 解题思维 递推是填表，每个状态只访问一次；记忆化递归是定义函数，遇到已算过的直接查表 O(1)，没算过的再算一次并存起来。只要状态空间相同且无重复计算，两种方法的状态访问次数都是 O(状态数)，时间复杂度自然相同。

🪤 陷阱拆解 B 选项的陷阱有三：第一，混淆了「无记忆化递归」（指数级）和「记忆化递归」（线性级）；第二，偷换概念——题目只问时间复杂度，不问空间复杂度；第三，利用考生对递归函数调用栈的恐惧心理，暗示递归一定慢。

🔄 反命题思维 命题人想考的是「实现方式不影响渐近时间复杂度」这一本质。如果改成「当状态依赖构成环时，哪种写法更优？」答案就变了——递推无法处理环，记忆化递归会死循环（除非加访问标记）。刷到类似题先问自己：题目到底在比较什么？是时间、空间，还是实现难度？