GESP 七级 · GESP 七级样题（C++ 组）第 21 题

判断题 · 答案 A · 考点：动态规划、STL算法基础

题目

动态规划最终要推导出状态转移方程才能求解。（）

答案：A

这道题考动态规划的核心定义。拿到判断题别急着翻书背定义，直接想：动态规划的本质是什么？是‘分而治之’把大问题拆成小问题，然后怎么把这些小问题的解拼起来？答案就是状态转移方程，它是DP的骨架，没有它DP就散了。

学生容易把DP和贪心、分治搞混，以为只要能写出递推式就行，不必是‘状态转移方程’；或者被‘最终’这个词吓到，觉得这是绝对化表述就选错。其实命题人就是利用这种对概念边界的模糊认知设坑——DP的状态转移方程可以很简单（比如斐波那契的f[i]=f[i-1]+f[i-2]），但它是必需的。

【考点】动态规划｜状态转移方程｜算法基础

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

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