GESP 七级 · GESP 202512 C++ 七级第 20 题

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

题目

求两个长度为 $ n $ 序列的最长公共子序列（LCS）长度时，可以使用滚动数组将空间复杂度从 $ O(n^2) $ 优化到 $ O(n) $。

答案：A

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

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

【考点】动态规划｜滚动数组优化｜最长公共子序列

本题考查 GESP 七级 C++ 大纲中"动态规划"模块的核心考点。命题人专门设置这道判断题，就是要卡住那些只背过"滚动数组能省空间"这行结论、却从未真正动手推导过依赖关系的考生。七级难度要求对 DP 状态转移的内存需求有精确理解，而非泛泛而谈。

第 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伴学里做这道题

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