GESP 八级 · GESP202609 C++ 八级第 24 题

判断题 · 答案 A · 考点：动态规划

← 整套速查表 GESP 八级全部真题

题目

使用滚动数组优化动态规划时，通常只能降低空间复杂度，不能降低时间复杂度。

答案：A

考点

动态规划讲解 →动态规划真题汇总 →

解题思维

滚动数组的本质是压缩存储维度，用循环变量覆盖旧状态。时间复杂度取决于状态数和转移次数，与存储方式无关。因此滚动数组只能降空间、不降时间，答案选 A。

常见错误

学生常把"优化"等同于"提速"，误以为少存数据就能少运算。其实滚动数组只是把二维表压成一维，转移逻辑不变，状态数没变，时间复杂度自然不变。

详细解析（节选）

1. 考纲定位

本题考查《GESP 考试大纲》动态规划模块的空间优化子知识点。命题人放这道题，就是要卡住那些只背"滚动数组能优化"却不清理"优化什么"的模糊认知——空间和时间是两个独立维度，混为一谈是绝大多数考生的通病。

2. 解题思维

看到"滚动数组"四个字，先定位到 DP 的空间压缩技巧。滚动数组的核心是用循环变量覆盖旧状态，比如一维数组 dp[i] 在迭代中只保留当前层和上一层的值，把二维表压成一维。但这里的关键观察是：时间复杂度由状态数和转移次数决定，与存储方式无关。无论存成二维还是压缩成一维，需要计算的状态个数没变，每个状态的转移操作也没变，所以时间复杂度不可能降低。答案只能是 A。

同考点真题

第 27 题· NOIP 2009 普及组初赛试题 · 答案 0tmp+a[i]==ans a[i]+tmp==ans ans==a[i]+tmp<0itmp+=a[i] tmp=tmp+a[i]看解析 →
第 28 题· NOIP 2010 普及组初赛试题 · 答案 num <= 2num < 3num == 2go(LEFT_TO_RIGHT)pos[i] == LEFTLEFT == pos[i]hour[i] + go(RIGHT_TO_LEFT)go(RIGHT_TO_LEFT) + hour[i]pos[i] = LEFT看解析 →
第 29 题· NOIP 2010 提高组初赛试题 · 答案 opt[k]home[r] = kj = i + i（或j = 2 * i 或j = i * 2）swap(i, j)（或swap(j, i)）value[i] + heap[1]（或heap[1] + value[i]）i - m看解析 →
第 15 题· CSP 2019 提高级第一轮 · 答案 A看解析 →
第 20 题· CSP 2019 提高级第一轮 · 答案 CBAD看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。

去刷题先做一次 AI 学情诊断

GESP 八级 · GESP202609 C++ 八级 第 24 题

题目

考点