GESP 六级 · GESP 202503 C++ 六级 第 22 题

在动态规划解决一维硬币找零问题时，若硬币面额为 $[1, 3, 4]$，目标金额为 $6$，则最少需要 2 枚硬币（$3+3$）。

动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。

DP 的难点在于状态定义。定义太大会超时，定义太小会漏掉最优解。注意初始化和边界条件。

【考点】动态规划｜一维数组 DP｜贪心反例

本题考查 GESP 六级“动态规划”模块经典题型——一维硬币找零。命题人并非单纯考察公式记忆，而是卡住大量考生对“贪心是否普适”的迷思。许多选手看到 3+3=6 便草率选 A，却忽略 DP 才是求最优解的通用工具。

解题链：定义 dp[i] 为凑出金额 i 所需最少硬币数，初始 dp[0]=0，其余为无穷大。状态转移方程为 dp[i] = min(dp[i], dp[i-c] + 1)，遍历每个硬币 c ∈ [1,3,4] 更新表。计算可知 dp[6]=2（由 dp[3]+1 或 dp[3]+1 得到，对应 3+3），故表述正确。通法：此类“固定面额求最优”问题，一维 DP 表是标准解法，无论面额如何，只需按此模板填充。

陷阱拆解：选项 B 的诱惑在于“贪心直觉”。若错误地先选最大面额 4，则剩余 2 需两枚 1，共 3 枚；若先选 3，剩 3 再选 3，得 2 枚。命题人利用“局部最优≠全局最优”的误区，诱导未系统训练 DP 的考生误判。更阴险的是，题目中“最少需要 2 枚”是结论，而非过程，考生若未验证 DP 表，仅凭记忆"3+3=6"便选 A，实则混淆了“存在一种方案”与“最优方案”。

反命题视角：若将面额改为 [1,2,5]，目标仍为 6，DP 表得 dp[6]=2（5+1），答案仍为 A；若目标改为 10，dp[10]=3（5+5），答案则变 B。命题人常在此类变体上设坑，考察考生是否真正掌握 DP 状态转移而非死记硬背。刷到类似题，先问：“面额集合变了，最优解是否同步变化？”