硬币找零问题用一维dp[i]而非二维，因只求最少硬币数；dp[i]表示凑出金额i的最少硬币数，初始化dp[0]=0、其余为amount+1，避免溢出和误判；需过滤无效硬币并检查dp[i-c]是否可达。
硬币找零问题的 DP 状态定义为什么是 dp[i] 而不是 dp[i][j]
因为题目通常只要求「最少硬币数」，而非「方案数」或「是否恰好凑成」的多维判断，所以一维状态足够。设 dp[i] 表示凑出金额 i 所需的最少硬币数，初始时 dp[0] = 0，其余设为一个大值（如 INT_MAX 或 amount + 1），避免溢出。
常见错误是把 dp 初始化为 -1 或 0：前者导致后续更新逻辑混乱，后者会让未可达状态被误认为“只需 0 枚硬币”。
-
dp数组大小必须是amount + 1，下标要覆盖0到amount - 若最终
dp[amount]仍为初始大值，说明无法凑出，返回-1 - 硬币数组
coins中可能含重复值或0，需提前过滤：if (c amount) continue;
状态转移时为什么要用 dp[i - c] != INT_MAX 做安全检查
直接写 dp[i] = min(dp[i], dp[i - c] + 1) 会触发整数溢出：当 dp[i - c] 是 INT_MAX 时，加 1 变成负数，导致结果错误。这不是理论假设——实际输入如 coins = {2}、amount = 1 就会走到 i=1, c=2 的分支外，但若没过滤 c > i，仍可能访问 dp[-1]（越界）或误用溢出值。
- 推荐初始化为
dp[i] = amount + 1（而非INT_MAX），这样dp[i - c] + 1不会溢出，且amount + 1天然大于任何合法解（最多用amount枚面值为 1 的硬币） - 循环内务必加
if (c ，跳过当前硬币过大情况 - 不要在循环外对
coins排序——DP 不依赖顺序，排序反而可能误导调试
为什么自底向上填表比记忆化递归更稳妥
记忆化递归（dfs(i)）写起来直观，但容易栈溢出（amount 达 1e4 时递归深度可能超限），且忘记剪枝 if (i 会导致无限调用。而迭代版空间可控、边界清晰，更适合生产环境。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
示例核心循环：
for (int i = 1; i <= amount; ++i) {
for (int c : coins) {
if (c <= i && dp[i - c] != amount + 1) {
dp[i] = min(dp[i], dp[i - c] + 1);
}
}
}
- 内层循环顺序无关，
coins顺序不影响结果 - 若需返回具体方案（哪些硬币），需额外维护
parent[i]记录最后选的硬币值，回溯重构路径 - 时间复杂度
O(amount * coins.size())，空间O(amount)；若硬币种类极少（如固定几种面额），可考虑完全背包优化，但一般无需
测试时最容易漏掉的边界 case 有哪些
不跑这几个，代码大概率线上失败：
-
amount = 0→ 应返回0（空集） -
coins = {1},amount = 10000→ 检查是否 OOM 或超时（确保没递归、数组分配合理） -
coins = {2},amount = 1→ 必须返回-1，验证不可达逻辑 -
coins = {1, 2, 5},amount = 11→ 正确答案是3（5+5+1），验证状态转移无偏移
硬币面额本身没有单调性要求，但若含负数或零，必须在输入处理阶段抛异常或过滤——DP 前提是所有 c > 0。
