GESP 七级 · GESP 202312 C++ 七级第 23 题

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

题目

动态规划只要推导出状态转移方程，就可以写出递归程序来求出最优解。（）

答案：B

这题考动态规划的本质理解，核心是：状态转移方程只是定义了‘怎么算’，但没解决‘算多少次’的问题。拿到题先想：递归不加记忆化会怎样？指数级爆炸就是答案。

学生常误以为‘有方程就能算出最优解’，忽略了递归实现时的时间复杂度问题。命题人爱用‘只要…就…'这种绝对化表述挖坑，诱导背公式的人选对。容易错选A，因为没意识到朴素递归在重叠子问题下会重复计算，导致超时。

GESP七级算法模块，考查对动态规划核心思想的理解深度。命题人特意设置这道判断题，就是要区分‘会写方程’和‘能求出最优解’之间的鸿沟。

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

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