GESP 七级 · GESP 202503 C++ 七级 第 24 题

动态规划算法通常有递归实现和递推实现。但由于递归调用在运行时会由于层次过多导致程序崩溃，有些动态规划算法只能用递推实现。

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

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

【考点】动态规划｜递归与栈溢出｜递推实现

🎯 考纲定位：本题出自《GESP 七级 数据结构与算法》模块，核心考查"递归实现动态规划时栈深度上限"这一隐性考点。命题人特意放这道判断题，就是要筛掉那些只会背 DP 公式、却不懂递归调用栈机制的考生——他们往往在真实竞赛里遇到深度超过系统栈的 DP（如斐波那契递归实现）就 RE，而本题正是用极简形式暴露这个致命弱点。

🧠 解题思维：看到"递归实现会崩溃"立刻联想到函数调用栈的 O(1) 空间消耗——每层递归压栈一次，深度为 O(N) 的 DP（如斐波那契递归）栈帧数轻松爆炸。递推实现本质是"自底向上填表"，用循环替代递归，栈空间降为 O(1)。这类题的通法：遇到任何 DP 先问"递归深度能否受控"？若深度与 N 同阶，则必须用递推或尾递归优化；若深度是 O(log N)（如记忆化搜索树形 DP），递归通常可接受。

🪤 陷阱拆解：选 B 的考生通常陷入两个思维误区。其一，把"动态规划"笼统理解为"有递归版就有递推版"，忽略了递归深度与系统栈空间的硬性约束（如 Windows 默认栈 1MB，递归深度>10^5 必爆栈）；其二，对"只能"这种绝对化表述不敏感，误以为只要存在递推实现就否定原命题。本题最阴险的细节是"只能"——它限定了"存在某些 DP 算法，递归版绝对不可行"，而非"所有 DP 都只能递推"。若你只背结论"DP 有递推实现"，而不理解栈溢出本质，就会把绝对化表述当成陷阱而错选 B。

🔄 反命题思维：若把题干改成"所有动态规划算法都能用递归实现"，答案立刻翻盘——因为斐波那契、爬楼梯等经典 DP 递归深度 O(N) 必爆栈。刷到这类题先自问：命题人想考我"递归深度与栈空间的关系"，还是"DP 的实现多样性"？前者才是本题真正的区分度所在。