freeCodeCamp 每日编程挑战 334「Exact Change」用动态规划求解硬币找零方案数【免费下载链接】freeCodeCampfreeCodeCamp.orgs 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 ChangeChallenge 334 是 freeCodeCamp 每日编程挑战Daily Coding ChallengeJavaScript 系列中的第 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四种硬币凑出该金额的不同方案总数。这里有几个关键约束需要明确金额单位是美分输入为整数例如17代表 17 美分硬币可以无限次重复使用每种面额数量不受限只统计组合而非排列用 1 分硬币凑 2 美分只有11一种方案而如果用排列计数(1,1)的不同排列会被重复计算不同方案是指硬币面额的多重集合不同与硬币被拿出的先后顺序无关。该挑战文档位于 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 组输入输出对它们既是题目的验收标准也是我们验证实现正确性的依据输入amount美分期望返回值说明31只有111一种凑法921×9与51×4两种凑法176使用 1/5/10/25 的 6 种组合3924组合数随金额增大而快速增长6173组合数增长呈超线性特征99213接近 1 美元时的方案总数文档中以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 为什么外层枚举硬币、内层递增——这是组合计数的关键外层循环枚举面额意味着对于每一种面额一次性处理完它在所有金额上的贡献再进入下一种面额。这样任意一个方案中的硬币顺序被压平为按面额分组天然避免了(15)与(51)被当成两种方案——因为面额 1 的全部贡献在处理面额 5 之前已经完成后续不会再回头用面额 5 去补面额 1 的组合。这是题目要求distinct ways / 不同方案的根本保证。内层循环从小到大递增允许同一面额的硬币重复使用当i增长时dp[i - coin]可能已经包含使用多枚coin的方案于是dp[i]就能统计再用一枚的情况对应了硬币无限量的约束。4.3 手工验证一组数据amount 9面额处理阶段dp 数组关键变化初始化dp [1, 0, 0, ..., 0]处理 1 分每个金额都有且仅有全部用 1 分一种方案dp[9] 1处理 5 分从i5起累加dp[i-5]得到dp[9] 1 dp[4] 2最终dp[9] 2对应1×9与51×4两种方案与文档断言一致。4.4 复杂度分析时间复杂度O(coins.length × amount)对本题即为O(4 × amount)线性级别amount 99时开销极小空间复杂度O(amount)只需一维数组这也是相比二维 DP 的显著优势。4.5 边界情况与进阶思考若amount 0dp[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.tsGET /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 仓库工作区内进行阅读题目与测试直接打开 挑战文档将# --solutions--中的实现复制到你的编辑器或用下面任意一种等价实现用 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}\); } 输出预期6 个用例全部输出PASS即与文档断言完全一致进阶练习把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.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考