企业官网建设流程全解析

freeCodeCamp 每日编程挑战 334「Exact Change」：用动态规划求解硬币找零方案数

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp

本篇技术指南以 freeCodeCamp 开源仓库中 Challenge 334: Exact Change 的挑战文档为核心，完整讲解这道经典"硬币找零"计数问题的题意、测试约定、参考实现与底层算法原理。读完本文，你将掌握用一维动态规划（DP）统计"无顺序、可重复使用硬币"的组合方案数的标准写法，理解为什么遍历顺序决定了"组合"而非"排列"，并能把同一套模板迁移到其他货币面额与约束场景中。

一、挑战题目解读：什么是 Exact Change

Challenge 334 是 freeCodeCamp 每日编程挑战（Daily Coding Challenge）JavaScript 系列中的第 334 题。原文档给出的题目描述非常精炼：

Given an integer amount in cents, return the number of distinct ways to make exact change using pennies (1 cent), nickels (5 cents), dimes (10 cents), and quarters (25 cents).

即：给定一个以"美分"为单位的整数金额，返回使用1 分（penny）、5 分（nickel）、10 分（dime）、25 分（quarter）四种硬币凑出该金额的不同方案总数。

这里有几个关键约束需要明确：

1. 金额单位是美分，输入为整数，例如17代表 17 美分；
2. 硬币可以无限次重复使用（每种面额数量不受限）；
3. 只统计"组合"而非"排列"：用 1 分硬币凑 2 美分，只有1+1一种方案；而如果用排列计数，(1,1)的不同排列会被重复计算；
4. "不同方案"是指硬币面额的多重集合不同，与硬币被拿出的先后顺序无关。

该挑战文档位于 curriculum/challenges/english/blocks/daily-coding-challenges-javascript/6a1d9f98e819ed70a0e994e0.md，属于daily-coding-challenges-javascript区块。从区块配置 curriculum/structure/blocks/daily-coding-challenges-javascript.json 可以看到，该区块的helpCategory为JavaScript、blockLayout为legacy-challenge-list、并启用了usesMultifileEditor（多文件编辑器），说明这类题目在 freeCodeCamp 平台上是作为每日一道、按日期推进的编程练习来运行的。

二、测试约定（hints）：题目要求的精确输出

原文档的# --hints--部分给出了 6 组输入输出对，它们既是题目的验收标准，也是我们验证实现正确性的依据：

文档中以assert.equal(exactChange(3), 1)这类断言形式给出了 6 个测试用例：

assert.equal(exactChange(3), 1); assert.equal(exactChange(9), 2); assert.equal(exactChange(17), 6); assert.equal(exactChange(39), 24); assert.equal(exactChange(61), 73); assert.equal(exactChange(99), 213);

从这些断言可以看出，测试只检查exactChange函数的返回值，不限制内部实现方式，因此你可以自由选择递归、记忆化搜索或动态规划等方案，只要结果正确即可通过。

三、起始代码（seed）与解题函数签名

原文档的# --seed--部分给出了参赛者的起始代码：

function exactChange(amount) { return amount; }

• 函数名为exactChange，必须保留，因为测试断言直接调用它；
• 唯一的参数是amount（整数，单位为美分）；
• 起始实现直接返回amount，显然无法通过测试，需要你补全算法；
• 题目未规定输入范围，但从测试用例（最大99）与典型实现来看，应能正确处理正整数金额（包括0或较小金额的边界情况）。

四、参考解法：一维动态规划（官方 solutions）

原文档的# --solutions--部分给出了官方参考实现，这正是经典的一维 DP 写法：

function exactChange(amount) { const coins = [1, 5, 10, 25]; const dp = new Array(amount + 1).fill(0); dp[0] = 1; for (const coin of coins) { for (let i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; }

4.1 算法核心：状态与转移

• dp[i]表示用当前已枚举过的硬币面额凑出金额i的方案数；
• 初始化dp[0] = 1：凑出 0 美分只有"什么都不用"这一种方案（这是所有 DP 递推的起点）；
• 外层循环枚举硬币面额coin，内层循环从coin递增到amount；
• 状态转移方程：dp[i] += dp[i - coin]，含义是"凑出金额i的方案数，加上凑出金额i - coin的方案数（每套方案再补上一枚coin）"。

4.2 为什么外层枚举硬币、内层递增——这是"组合计数"的关键

• 外层循环枚举面额意味着：对于每一种面额，一次性处理完它在所有金额上的贡献，再进入下一种面额。这样任意一个方案中的硬币顺序被"压平"为按面额分组，天然避免了(1+5)与(5+1)被当成两种方案——因为面额 1 的全部贡献在处理面额 5 之前已经完成，后续不会再回头用面额 5 去"补"面额 1 的组合。这是题目要求"distinct ways / 不同方案"的根本保证。
• 内层循环从小到大递增允许同一面额的硬币重复使用：当i增长时，dp[i - coin]可能已经包含使用多枚coin的方案，于是dp[i]就能统计"再用一枚"的情况，对应了"硬币无限量"的约束。

4.3 手工验证一组数据：amount = 9

最终dp[9] = 2，对应1×9与5+1×4两种方案，与文档断言一致。

4.4 复杂度分析

• 时间复杂度：O(coins.length × amount)，对本题即为O(4 × amount)，线性级别，amount = 99时开销极小；
• 空间复杂度：O(amount)，只需一维数组，这也是相比二维 DP 的显著优势。

4.5 边界情况与进阶思考

• 若amount = 0，dp[0] = 1，返回 1，语义上对应"空方案"；
• 若某金额小于最小面额 1 分（现实中不存在，但若面额含非 1 的最小币值），无法凑出的金额保持 0，返回 0 即可；
• 扩展到其他面额：只要把coins数组替换为任意整数面额列表，算法无需改动即可通用，例如欧元分币或自定义游戏货币；
• 改为"排列计数"：只需交换内外循环顺序（外层遍历金额、内层遍历硬币），得到的结果就变成了考虑顺序的方案总数，这是面试中常见的变体追问。

五、从仓库源码看每日挑战的运行机制

Challenge 334 并非孤立的一道题，它是 freeCodeCamp 每日编程挑战体系中的一环。结合仓库源码，可以从三个层面理解它如何被"生产、分发、校验"。

5.1 题目如何组织：区块与顺序

在 curriculum/structure/blocks/daily-coding-challenges-javascript.json 中，6a1d9f98e819ed70a0e994e0被登记为Challenge 334: Exact Change，前后分别是 Challenge 333 "Issue Triage 2" 与 Challenge 335 "Five Dice"。该文件是区块元数据（block metadata），记录了challengeOrder中每个挑战的id与title，而挑战的完整题目、测试与解法则存放在curriculum/challenges/english/blocks/daily-coding-challenges-javascript/目录下对应的 Markdown 文件中。

5.2 题目如何校验：challengeType 与测试系统

Challenge 334 的 frontmatter 中标明challengeType: 28。在 packages/shared/src/config/challenge-types.ts 中，dailyChallengeJs属于每日编程挑战类型集合，getIsDailyCodingChallenge通过challengeType判断某挑战是否为每日挑战，getDailyCodingChallengeLanguage则把dailyChallengeJs映射到语言标识'javascript'。原文档# --hints--中的assert.equal(...)断言，会被课程构建链路（curriculum包的 schema 校验与测试运行器）转换成对用户提交函数的运行时校验。

5.3 题目如何发布：每日种子脚本

仓库中的 tools/daily-challenges/seed-daily-challenges.ts 展示了每日挑战的发布机制：脚本从 GraphQL 拉取 dev-playground 区块中的挑战数据，写入 MongoDB 的DailyCodingChallenges集合，并校验 JavaScript 与 Python 两套挑战数量一致（期望为 365 道，即全年每天一道）。起始日期被硬编码为2025-08-11，且代码明确注释"发布后不应修改"。也就是说，Challenge 334 与相邻题目一样，按日期顺序依次成为"当天的每日一题"。

5.4 题目如何分发：API 路由

API 层提供了按日期获取每日挑战的只读接口，实现在 api/src/daily-coding-challenge/routes/daily-coding-challenge.ts：

• GET /daily-coding-challenge/today：返回今日挑战；
• GET /daily-coding-challenge/date/:date：按YYYY-MM-DD查询某日挑战，且不会返回晚于"美国中部时间当天"的未来题目；
• GET /daily-coding-challenge/day/:day：按MM-DD查询（自动映射到正确的年份）；
• GET /daily-coding-challenge/month/:month：按YYYY-MM查询整个月的挑战列表；
• GET /daily-coding-challenge/all：列出全部已发布挑战；
• GET /daily-coding-challenge/newest：返回最新挑战日期。

对应的请求/响应 schema 定义在 api/src/daily-coding-challenge/schemas/daily-coding-challenge.ts，其中singleChallengeResponse包含id、date、challengeNumber、title、description以及按语言组织的tests与challengeFiles。Challenge 334 的description、assert测试与起始代码，正是通过这一链路被下发到前端的。

5.5 前端如何展示：Daily Coding Challenge 组件

客户端在 client/src/components/daily-coding-challenge/ 下提供了日历（calendar.tsx）、小组件（widget.tsx）、未找到页（not-found.tsx）等组件来渲染每日挑战入口，用户在页面上作答后，提交仍走主 API 的挑战完成路由。挑战本身的编辑器遵循区块配置中的usesMultifileEditor: true，即使用多文件编辑器。

六、动手验证：如何在本地跑通这道题

如果你想在本地亲手验证本文的实现，可以参考以下步骤（均在 freeCodeCamp 仓库工作区内进行）：

1. 阅读题目与测试：直接打开 挑战文档，将# --solutions--中的实现复制到你的编辑器，或用下面任意一种等价实现；
2. 用 Node.js 快速验证（任意目录，无需依赖仓库构建）：

node -e " function exactChange(amount) { const coins = [1, 5, 10, 25]; const dp = new Array(amount + 1).fill(0); dp[0] = 1; for (const coin of coins) { for (let i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; } const cases = [[3,1],[9,2],[17,6],[39,24],[61,73],[99,213]]; for (const [input, expected] of cases) { const got = exactChange(input); console.log(\`exactChange(\${input}) = \${got} (expected \${expected}) \${got === expected ? 'PASS' : 'FAIL'}\`); } "

3. 输出预期：6 个用例全部输出PASS，即与文档断言完全一致；
4. 进阶练习：把coins换成[1, 2, 5, 10, 20, 50]（欧元分币）或[1, 3, 4]等自定义面额，观察结果变化；再尝试交换内外循环顺序，对比"组合计数"与"排列计数"的差异。

七、总结

Challenge 334「Exact Change」是一道将经典算法原型（无顺序硬币找零计数）封装进 freeCodeCamp 每日挑战体系的小题，但它承载的知识点却非常典型：

• 问题本质：带无限供给的整数组合计数问题（unbounded coin change counting）；
• 标准解法：一维 DP + 面额外层循环，dp[i] += dp[i - coin]，时间复杂度O(n × amount)、空间复杂度O(amount)；
• 易错点：内层循环的方向与内外层顺序，直接决定结果是"组合"还是"排列"；
• 工程全景：从 区块元数据、挑战文档、类型定义、种子脚本 到 API 路由 与 前端组件，可以看到一道每日挑战从课程内容到线上发布再到用户作答的完整闭环。

掌握了这题，你就掌握了"组合计数类 DP"的标准模板——无论是 LeetCode 上的518. Coin Change II，还是各类找零/凑数问题，都可以直接复用这套思路。

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp