GESP 八级 · GESP 202312 C++ 八级 第 21 题

动态规划算法的时间复杂度一般为：必要状态的数量，乘以计算一次状态转移方程的时间复杂度。

这题考动态规划时间复杂度构成。拿到题先想：DP 把大问题拆成多少个子问题（状态数），再想解每个子问题要几步（转移代价），两者相乘就是总耗时，这就是乘法原理在算法分析里的直接应用。

学生最容易把‘状态转移方程的时间复杂度’误当成‘整个 DP 算法的时间复杂度’，或者死记 O(n²)/O(n³) 而忽略状态空间大小。题干用‘一般为’留有余地，但选项 B 却用绝对化表述误导人，背结论的人容易忽略‘状态数×转移时间’的乘法结构，从而选错。

1. 考点与概念

动态规划的核心是把原问题拆解成若干子问题，每个子问题对应一个状态。时间复杂度由两部分决定：状态空间大小（有多少个不同子问题）和计算一次状态转移方程的代价（求一个状态需要多少步）。总复杂度＝状态数×单次转移时间，这是乘法原理在算法分析里的直接应用。

2. 命题视角

命题人卡住的是考生对‘时间复杂度构成’的模糊认知——很多人以为 DP 就是 O(n²) 或 O(n³)，不懂状态与转移的关系。题干用‘一般为’留有余地，但选项 B 却把‘状态转移方程的时间复杂度’偷换成‘DP 算法的整体时间复杂度’，利用考生对 O(n²) 的刻板印象制造陷阱。背结论的人容易忽略‘状态数×转移时间’的乘法结构，从而选错。