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

动态规划方法将原问题分解为一个或多个相似的子问题，因此必须使用递归实现。

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

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

【考点】动态规划实现｜递归与迭代思想。命题人旨在卡住GESP 202506 C++ 七级考生对DP实现方式的刻板印象——以为“分治=递归”，却忘了DP最经典的自底向上迭代写法，此题专治只会背结论不会看本质的“伪DP党”。

看到“分解子问题”先联想DP本质，但后半句“必须用递归”是逻辑陷阱。关键观察：DP的递推关系可以用数组迭代求解（自底向上），无需递归调用。这类题通法是“识别绝对化表述+寻找反例”，比如斐波那契数列既可是递归（带记忆化），也可是循环迭代，命题人专抓死记硬背者。

每个错误选项都设计了绝对化陷阱——“必须用递归”偷换了“可以使用递归”的概念。命题人利用的是考生对DP的暴力记忆：一听到“分治”就默认是递归。其实DP的迭代版本（自底向上填表）才是考场更常见的写法，如果你只背结论、不理解本质，就会掉进这个陷阱。

若把“必须”改成“可以”，答案就变A；若把“递归”改成“迭代”，答案仍是B。刷到类似题先问自己“命题人想考我什么”——是考DP的两种实现方式，还是考“分治必然递归”的谬误。