GESP 六级 · GESP 202409 C++ 六级第 14 题

选择题 · 答案 B · 考点：动态规划

题目

动态规划通常用于解决（）。

答案：B

贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。

贪心算法需要严格证明正确性。典型错误：局部最优不等于全局最优。例如0-1背包问题就不能用贪心。

【考点】动态规划定义｜最优子结构｜重叠子问题

GESP 六级《算法设计》模块第 3 章"动态规划"开篇第一道概念题。命题人卡住的是概念辨析能力——六级考生最容易把 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伴学里做这道题

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