PTA『凑零钱』题解：用动态规划找最小序列，保姆级代码逐行解析

PTA『凑零钱』题解动态规划实战与最小序列回溯技巧每次面对PTA平台的动态规划题目总会有种看山是山看山不是山最后看山还是山的顿悟体验。这道凑零钱问题看似简单却完美展现了动态规划从状态定义到路径回溯的完整思维链条。不同于普通背包问题只需输出最优解数值它要求我们找到字典序最小的具体方案——这就像在迷宫中不仅要找到出口还要记录下最优美的那条路径。1. 问题本质与建模思路这道题表面是货币组合问题实则是0-1背包的变种。给定N种面额的硬币和总金额M需要判断能否用这些硬币恰好凑出M元并要求当解存在时输出字典序最小的硬币序列。关键洞察点在于字典序最小意味着我们需要优先使用面额较小的硬币必须恰好凑出M元而非不超过M元需要记录选择路径而不仅仅是最终结果示例输入 8 9 5 9 8 7 2 3 4 1 示例输出 1 3 5为什么不是234因为135和234都满足总和为9但1开头的序列字典序更小。这种细微差别正是解题的精妙之处。2. 动态规划状态设计我们采用二维DP数组dp[i][j]表示前i种硬币凑出金额j的最大可能值。与标准背包不同这里需要同步维护选择矩阵x[i][j]记录决策路径。2.1 状态转移方程对于每个硬币arr[i]和金额j存在两种选择不选当前硬币dp[i][j] dp[i-1][j]选择当前硬币dp[i][j] dp[i-1][j-arr[i]] arr[i]取两者中的较大值更新DP表同时用x[i][j]标记选择行为if(dp[i-1][j-arr[i]]arr[i] dp[i-1][j]) { dp[i][j] dp[i-1][j-arr[i]]arr[i]; x[i][j] 1; // 标记选择 } else { dp[i][j] dp[i-1][j]; }2.2 预处理排序技巧为实现最小字典序需要将硬币降序排列。这样在回溯阶段会优先考虑小面额硬币bool cmp(int a, int b) { return a b; } // ... sort(arr1, arrN1, cmp);这种逆向排序保证了在相同解的情况下较小面额的硬币会较晚被考虑从而在回溯时能优先被选中。3. 路径回溯与解输出当dp[N][M] M时说明解存在。此时通过x矩阵反向追踪选择路径3.1 回溯算法实现从右下角开始向左上方回溯收集被选中的硬币int j M; for(int i N; i 1; --i) { if(x[i][j]) { ans.push_back(arr[i]); j - arr[i]; } }3.2 结果格式化输出将结果容器中的硬币按顺序输出注意处理空格格式bool first true; for(auto coin : ans) { if(!first) printf( ); printf(%d, coin); first false; }4. 完整代码架构解析让我们拆解完整的解决方案理解各组件如何协同工作输入处理阶段读取硬币数量N和目标金额M读取各硬币面值并降序排序DP表填充阶段初始化dp和x数组双重循环填充状态表同步更新选择矩阵解判断与输出阶段检查最终状态是否达成目标回溯收集结果硬币格式化输出#include cstdio #include algorithm #include vector using namespace std; int arr[10005]; int dp[10005][105] {0}; int x[10005][105]; vectorint ans; bool cmp(int a, int b) { return a b; } int main() { int N, M; scanf(%d%d, N, M); for(int i 1; i N; i) scanf(%d, arr[i]); sort(arr1, arrN1, cmp); // DP表填充 for(int i 1; i N; i) { for(int j 1; j M; j) { if(j arr[i]) { if(dp[i-1][j-arr[i]] arr[i] dp[i-1][j]) { dp[i][j] dp[i-1][j-arr[i]] arr[i]; x[i][j] 1; } else { dp[i][j] dp[i-1][j]; } } else { dp[i][j] dp[i-1][j]; } } } // 结果处理 if(dp[N][M] ! M) { printf(No Solution); } else { int j M; for(int i N; i 1; --i) { if(x[i][j]) { ans.push_back(arr[i]); j - arr[i]; } } for(int i 0; i ans.size(); i) { if(i ! 0) printf( ); printf(%d, ans[i]); } } return 0; }5. 复杂度分析与优化方向该解法的时间复杂度为O(NM)空间复杂度也是O(NM)。对于PTA平台的测试用例规模完全足够但在实际工程应用中可能需要优化空间优化可降维至一维数组只需记录前一行状态剪枝策略当金额超过M时可提前终止内层循环并行计算DP表的行间具有独立性可并行处理# 空间优化后的伪代码 dp [0]*(M1) x [[0]*(M1) for _ in range(N1)] for i in range(1, N1): for j in range(M, arr[i]-1, -1): # 逆向遍历 if dp[j-arr[i]] arr[i] dp[j]: dp[j] dp[j-arr[i]] arr[i] x[i][j] 16. 常见错误与调试技巧在实现这类带路径记录的DP时容易遇到以下陷阱排序方向错误升序排列会导致字典序非最小状态转移条件不完整忘记处理j arr[i]的情况回溯逻辑颠倒应从右下往左上回溯而非相反边界条件遗漏未处理无解情况调试时可打印中间DP表和选择矩阵// 调试打印 printf(DP Table:\n); for(int i 1; i N; i) { for(int j 1; j M; j) { printf(%2d , dp[i][j]); } printf(\n); }7. 同类问题扩展掌握此解法后可解决一系列变种问题完全背包版凑零钱每种硬币无限供应组合总数统计计算凑出金额的所有可能方式数目多重背包版每种硬币有数量限制多维约束问题同时考虑金额和硬币数量限制以完全背包为例只需将内层循环改为正向遍历for(int j arr[i]; j M; j) { // 正向遍历 if(dp[j-arr[i]] arr[i] dp[j]) { dp[j] dp[j-arr[i]] arr[i]; x[j] 1; // 记录选择 } }在PAT考试中这类动态规划题目往往不是考察能否写出标准解法而是测试对问题变种的适应能力和对算法本质的理解深度。建议在理解基础解法后尝试用不同的状态表示和转移方程来解决同一问题比如将状态定义为使用前i种硬币凑出金额j的最小硬币数这能帮助培养灵活的算法思维。