经典题解析：1、2、5 凑 100，一共有多少种凑法

图 1：本文封面，从子问题累加到答案，就是这道题的全部骨架。

先说明属性：这是一篇经典题解析，题目出自本地历史面试资料，与任何公司的当前招聘无关。它是动态规划的入门形态，但淘汰率不低——因为一半人会把「组合」写成「排列」，答案虚高几个数量级还不自知。

想象面试现场：「有面额 1、2、5 的硬币，数量不限。凑出 100 一共有多少种凑法？顺序不同算同一种。」

核心结论一句话

这是完全背包的计数版。DP 三板斧：状态定义 dp[i] 表示凑出面额 i 的方案数；转移方程是把「用上硬币 c」的方案数 dp[i-c] 累加进 dp[i]；初始化 dp[0]=1，其余为 0。正确答案是 541。而整道题的分水岭只有一句话：硬币放外层循环。

为什么循环顺序值一半分数。

「外层硬币、内层面额」的含义是：先固定只用 1 元硬币，把 dp 整个扫一遍；再放开 2 元硬币，在已有结果上叠加；最后放开 5 元。这样每枚硬币在同一轮里可以被反复取用（内层从小到大扫，dp[i-c] 已经是「允许用 c」的最新值），而不同硬币的引入有先后次序，「1+2」和「2+1」只会在同一轮里被算一次——组合不计顺序，正是靠这个循环结构保证的。如果把两层循环对调（外层金额、内层硬币），每个金额都会把「先用 1 再用 2」和「先用 2 再用 1」各算一遍，组合就变成了排列，结果虚高。下面代码里两种写法都留着，对照看差异。

写出可运行代码并实测。

下面这份实现包含正解、循环对调的错误写法、暴力枚举对照，用 Node.js 22.15.0 直接运行（node coins.js）即可：

'use strict';

// 组合数 DP：外层硬币、内层面额，同一硬币可反复取用，组合不计顺序
function countWays(coins, target) {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1; // 凑出 0 有一种方案：什么都不选
  for (const c of coins) {              // 外层：先固定一种硬币
    for (let i = c; i <= target; i++) { // 内层：从小到大扫面额
      dp[i] += dp[i - c];               // 用上硬币 c 的方案数累加进来
    }
  }
  return dp[target];
}

// 对照 1：两层循环对调的错误写法（把排列误当组合，结果虚高）
function countPermutations(coins, target) {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= target; i++) {
    for (const c of coins) {
      if (i >= c) dp[i] += dp[i - c];
    }
  }
  return dp[target];
}

// 对照 2：暴力枚举核验（z 是 5 元枚数，y 是 2 元枚数，剩下全用 1 补齐）
function bruteForce(target) {
  let count = 0;
  for (let z = 0; z * 5 <= target; z++) {
    for (let y = 0; y * 2 + z * 5 <= target; y++) {
      count++; // 固定 z 和 y 后，1 元的补法恰好一种
    }
  }
  return count;
}

const cases = [0, 1, 2, 3, 5, 10, 20, 50, 100];
for (const t of cases) {
  const dp = countWays([1, 2, 5], t);
  const bf = bruteForce(t);
  console.log(`凑 ${t}：DP=${dp} 暴力=${bf} ${dp === bf ? 'OK' : 'FAIL'}`);
}
console.log('凑 100 组合数（正解）：', countWays([1, 2, 5], 100));
console.log('凑 100 排列数（循环对调的错误结果）：', countPermutations([1, 2, 5], 100));

实测输出：

凑 0：DP=1 暴力=1 OK
凑 1：DP=1 暴力=1 OK
凑 2：DP=2 暴力=2 OK
凑 3：DP=2 暴力=2 OK
凑 5：DP=4 暴力=4 OK
凑 10：DP=10 暴力=10 OK
凑 20：DP=29 暴力=29 OK
凑 50：DP=146 暴力=146 OK
凑 100：DP=541 暴力=541 OK
凑 100 组合数（正解）： 541
凑 100 排列数（循环对调的错误结果）： 9.119786900763293e+22

九个面额点全部对拍一致。错误写法的输出值得多看一眼：9.1×10²²，大到连双精度浮点都装不下精确值——排列和组合的差距不是几倍，是天文量级。这也是为什么「自测一个小数」很重要：凑 5 的组合数是 4（5；2+2+1；2+1+1+1；1×5），排列数却是 16，写成代码跑一遍，对错立刻显形。

图 2：DP 三板斧、循环顺序与一条迷你 dp 数组。

可能的追问与易错点。

「如果每种硬币只有限定枚数呢？」那就从完全背包退化成多重背包，内层循环要改成从大到小扫，或把枚数拆成二进制位展开成 0-1 背包——一句话点出「0-1 背包内层逆序、完全背包内层正序」即可。「如果问的是最少用几枚硬币呢？」计数变最优化：状态改成最少枚数，转移取 min，初始化改成无穷大，骨架不变。易错点有三：一是循环对调把排列当组合，上面已经实测过代价；二是初始化写成全 0，忘了 dp[0]=1 这个「什么都不选」的基准，所有转移都成了无源之水；三是面额 1 忘记处理边界——有了 1 任何金额都可解，没有 1 就要面对无解面额，dp 值保持 0 就是「凑不出」的自然表达。

回到面试现场，建议的答题节奏：先暴力枚举讲清问题语义（顺序不同算同一种），再给 DP 三板斧写出正解，然后主动补一句「硬币在外层是组合、金额在外层是排列」，最后用小数自验。这套「状态定义—转移方程—初始化」的建模语言不止属于硬币：序列解码的方案计数、路径规划的走法统计，骨架都是同一个。

你做 DP 题时踩过「组合写成排列」的坑吗？当时是怎么发现的？欢迎分享。