freeCodeCamp 每日编程挑战 252 解析Unique Stair Climber 爬楼梯问题的斐波那契式动态规划【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp本篇技术指南围绕 freeCodeCamp 开源仓库中的第 252 道每日编程挑战Daily Coding Challenge「Unique Stair Climber」展开它要求实现一个getUniqueClimbs函数统计每次走 1 级或 2 级台阶时爬上给定级数楼梯的全部不同走法。读完本文你将掌握这道经典爬楼梯问题的递推建模、斐波那契数本质、从朴素递归到迭代动态规划的完整演进路径以及它在 freeCodeCamp 仓库中的题目格式、测试断言与种子数据落地方式可直接在本地复现并验证。挑战定位这道题在仓库中的位置「Unique Stair Climber」是 freeCodeCamp 课程体系daily-coding-challenges-javascript模块中的第 252 题其完整题目文件位于 curriculum/challenges/english/blocks/daily-coding-challenges-javascript/69bc6cb30c1d112a2e110a09.md。题目文件采用 freeCodeCamp 挑战标准的 Markdown 前置元数据frontmatter结构--- id: 69bc6cb30c1d112a2e110a09 title: Challenge 252: Unique Stair Climber challengeType: 28 dashedName: challenge-252 ---其中challengeType: 28对应每日编码挑战daily coding challenge这一特殊挑战类型dashedName用于生成稳定 URL。在模块顺序配置 curriculum/structure/blocks/daily-coding-challenges-javascript.json 中该题以id为键按序登记Challenge 251 为 Array Sum FinderChallenge 253 为 Acronym Finder说明它是 365 道每日挑战序列中的一员与同模块其他题目共用usesMultifileEditor: true、helpCategory: JavaScript等块级配置。题目语义拆解题目的描述只有一句话Given a number of stairs, return how many distinct ways someone can climb them taking either 1 or 2 steps at a time.即给定楼梯级数steps一个人在每一步只能选择走 1 级或 2 级返回到达顶部所有不同走法的数量。注意这里的重点是 distinct ways不同走法走法的顺序是有意义的——先走 1 级再走 2 级与先走 2 级再走 1 级是两种不同的走法。以 4 级楼梯为例全部 5 种走法为1 1 1 11 1 21 2 12 1 12 2这正是题目测试断言getUniqueClimbs(4) 5的含义。递推关系的推导为什么答案是斐波那契数设f(n)表示爬n级楼梯的不同走法数。分析最后一步的动作如果最后一步走了1 级那么此前已经爬完n - 1级对应的走法数为f(n - 1)如果最后一步走了2 级那么此前已经爬完n - 2级对应的走法数为f(n - 2)。由于最后一步不可能同时既走 1 级又走 2 级两个子集互不重叠且覆盖了所有情况因此得到递推式f(n) f(n - 1) f(n - 2)再考察边界条件f(1) 1只有 1 级楼梯唯一走法是直接走 1 级f(2) 22 级楼梯有两种走法11 或直接 2 级。加上f(0) 1站在起点不迈步也是一种空走法作为递推的锚点数列展开为1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...。这正是从第 2 项开始的斐波那契数列——f(n)等于标准斐波那契数列1, 1, 2, 3, 5, ...的第n 1项。同模块的 Challenge 3 Fibonacci Sequence、Challenge 22 Tribonacci Sequence、Challenge 145 Nth Fibonacci Number 都与该递推思想同源可见斐波那契递推是每日挑战模块反复考察的核心模式。官方测试用例用断言锁定的行为规范题目文件的--hints--段落通过 6 组断言精确定义了函数的行为边界覆盖了从小到大、直至大规模输入的取值调用期望返回值getUniqueClimbs(4)5getUniqueClimbs(5)8getUniqueClimbs(10)89getUniqueClimbs(18)4181getUniqueClimbs(29)832040getUniqueClimbs(50)20365011074这些断言直接以可执行代码形式写在题目中例如assert.equal(getUniqueClimbs(4), 5);逐组核对可以发现f(4)5、f(5)8与上面手动展开的数列一致f(10)89是斐波那契第 11 项f(50)20365011074则验证了实现必须支持大规模输入。值得一提的是20365011074仍小于 JavaScript 的Number.MAX_SAFE_INTEGER9007199254740991因此官方测试用例在双精度浮点数范围内可精确表示无需引入BigInt——这与题目要求的普通数值返回类型保持一致。起点代码Seed题目为答题者提供了最小化的起点实现位于--seed--/--seed-contents--段function getUniqueClimbs(steps) { return steps; }这个占位实现仅原样返回steps显然无法通过任何测试。答题者的任务是在保留函数名与参数签名的前提下补全真正的走法统计逻辑。该函数名与签名正是 6 组测试断言所依赖的契约改动函数名或参数将导致断言直接失败。官方题解逐行剖析题目文件--solutions--段给出了官方参考实现采用**迭代动态规划滚动变量**写法function getUniqueClimbs(steps) { if (steps 0) return 0; if (steps 1) return 1; if (steps 2) return 2; let prev2 1, prev1 2; for (let i 3; i steps; i) { [prev2, prev1] [prev1, prev2 prev1]; } return prev1; }逐行解读其设计意图边界处理steps 0返回00 级或负数没有合法走法steps 1返回1steps 2返回2。这三个分支覆盖了递推的初始条件避免进入循环时访问未初始化的变量。状态初始化prev2 1对应f(0)prev1 2对应f(1)若把循环变量从 3 起步则prev2/prev1实际扮演f(i-2)/f(i-1)的角色。滚动迭代循环从i 3推进到steps每次用数组解构赋值[prev2, prev1] [prev1, prev2 prev1]一次性完成「旧值丢弃、新值接替」——prev1更新为prev2 prev1即f(i)同时prev2接住旧的prev1。这个技巧避免了引入临时变量写法紧凑且语义清晰。返回循环结束后prev1恰好是f(steps)。该实现的时间复杂度为O(n)单次线性扫描空间复杂度为O(1)仅两个变量是这道题在面试与刷题语境下的标准最优解。算法演进从朴素递归到迭代官方题解并非唯一路径理解从朴素到优化的演进能加深对动态规划「重叠子问题」本质的认识。朴素递归指数级仅作推导示意直接照搬递推式f(n) f(n-1) f(n-2)会形成指数级调用树例如getUniqueClimbs(50)需要约2^50量级的重复计算实际运行会卡死且容易在递归深度上逼近调用栈上限function getUniqueClimbs(steps) { if (steps 0) return 0; if (steps 1) return 1; if (steps 2) return 2; return getUniqueClimbs(steps - 1) getUniqueClimbs(steps - 2); }记忆化递归自顶向下O(n) 时间用数组缓存已计算的子问题把每个f(i)只算一次时间复杂度降为O(n)但空间仍为O(n)function getUniqueClimbs(steps) { const memo new Array(steps 1).fill(0); memo[1] 1; memo[2] 2; const climb n { if (n 0) return 0; if (memo[n] ! 0) return memo[n]; memo[n] climb(n - 1) climb(n - 2); return memo[n]; }; return climb(steps); }自底向上迭代官方方案由于f(n)只依赖前两个值无需保留整个数组滚动变量把空间压到O(1)。这正是官方题解选择的工程化平衡点代码量小、无递归栈风险、可线性处理到steps 50甚至更大。在仓库中的运行与验证这道题并非孤立的一个 Markdown 文件而是完整「内容生产 — 数据库 — API 分发 — 前端展示」链条中的一环。题目校验仓库的课程测试框架会对--hints--中的断言执行求值。daily-coding-challenges-javascript块配置了disableLoopProtectTests: true同时模块级测试位于 curriculum/src/test/daily-challenges.test.js用于在内容侧验证每日挑战的格式与断言可执行性。种子数据生成每日挑战由脚本 tools/daily-challenges/seed-daily-challenges.ts 从 Dev Playground 超级块经 GraphQL 拉取后写入 MongoDB 的DailyCodingChallenges集合脚本要求 JavaScript 与 Python 两个版本各恰好 365 道对应EXPECTED_CHALLENGE_COUNT 365并以2025-08-11为起点按天递增分配日期详见 tools/daily-challenges/README.md。种子数据中会同时携带该题的测试断言tests与起始代码challengeFiles数据结构由 client/src/utils/daily-coding-challenge-validator.ts 中的 Joi Schema 约束每个语言版本必须包含teststext testString与challengeFilesfileKey contents。API 分发客户端通过公开只读接口获取题目信息路由定义在 api/src/daily-coding-challenge/routes/daily-coding-challenge.ts包括按YYYY-MM-DD查询、按MM-DD查询、/today、按月列表、全部列表与最新日期等端点请求与响应结构由 TypeBox Schema 定义于 api/src/daily-coding-challenge/schemas/daily-coding-challenge.ts。日期处理工具 api/src/daily-coding-challenge/utils/helpers.ts 中实现了dateStringToUtcMidnight、monthDayStringToUtcDate、getSourceDate等函数负责把请求日期映射到 2025-08-11 至 2026-08-10 的原始挑战日期区间含 2 月 29 日映射到 2 月 28 日的闰年处理前端侧对应的日期工具在 client/src/components/daily-coding-challenge/helpers.ts。本地验证在本地克隆仓库后可在任意 Node 环境直接验证题解逻辑——将官方题解与断言复制到脚本中执行或用pnpm运行课程测试套件对daily-coding-challenges-javascript块做整体校验。注意每日挑战题目的在线提交仍走主挑战完成路由见 api/src/daily-coding-challenge/README.md公开 GET 接口仅用于读取题目信息。变体与延伸思考掌握这道题后可以自然迁移到以下变体允许走 1/2/3 级递推变为f(n) f(n-1) f(n-2) f(n-3)边界条件相应扩展滚动变量需要三个最小步数而非走法数问题从计数转为最优化可改用贪心或 DP 求最少步数代价约束每级台阶带权重时需要引入「到第 i 级的最小累计代价」状态输入规模扩展若测试用例逼近或超过Number.MAX_SAFE_INTEGER需切换为BigInt或字符串大数运算这也是同模块 String MathChallenge 249等题目专门考察的方向。从本质上看「Unique Stair Climber」是一道用最小代码量呈现「最优子结构 重叠子问题」两大 DP 特征的入门题官方提供的迭代滚动实现更是把空间复杂度压到常数的教科书范例值得作为复习动态规划时的最小自检用例。【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 freeCodeCamp 每日编程挑战 252 解析：Unique Stair Climber 爬楼梯问题的斐波那契式动态规划
freeCodeCamp 每日编程挑战 252 解析Unique Stair Climber 爬楼梯问题的斐波那契式动态规划【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp本篇技术指南围绕 freeCodeCamp 开源仓库中的第 252 道每日编程挑战Daily Coding Challenge「Unique Stair Climber」展开它要求实现一个getUniqueClimbs函数统计每次走 1 级或 2 级台阶时爬上给定级数楼梯的全部不同走法。读完本文你将掌握这道经典爬楼梯问题的递推建模、斐波那契数本质、从朴素递归到迭代动态规划的完整演进路径以及它在 freeCodeCamp 仓库中的题目格式、测试断言与种子数据落地方式可直接在本地复现并验证。挑战定位这道题在仓库中的位置「Unique Stair Climber」是 freeCodeCamp 课程体系daily-coding-challenges-javascript模块中的第 252 题其完整题目文件位于 curriculum/challenges/english/blocks/daily-coding-challenges-javascript/69bc6cb30c1d112a2e110a09.md。题目文件采用 freeCodeCamp 挑战标准的 Markdown 前置元数据frontmatter结构--- id: 69bc6cb30c1d112a2e110a09 title: Challenge 252: Unique Stair Climber challengeType: 28 dashedName: challenge-252 ---其中challengeType: 28对应每日编码挑战daily coding challenge这一特殊挑战类型dashedName用于生成稳定 URL。在模块顺序配置 curriculum/structure/blocks/daily-coding-challenges-javascript.json 中该题以id为键按序登记Challenge 251 为 Array Sum FinderChallenge 253 为 Acronym Finder说明它是 365 道每日挑战序列中的一员与同模块其他题目共用usesMultifileEditor: true、helpCategory: JavaScript等块级配置。题目语义拆解题目的描述只有一句话Given a number of stairs, return how many distinct ways someone can climb them taking either 1 or 2 steps at a time.即给定楼梯级数steps一个人在每一步只能选择走 1 级或 2 级返回到达顶部所有不同走法的数量。注意这里的重点是 distinct ways不同走法走法的顺序是有意义的——先走 1 级再走 2 级与先走 2 级再走 1 级是两种不同的走法。以 4 级楼梯为例全部 5 种走法为1 1 1 11 1 21 2 12 1 12 2这正是题目测试断言getUniqueClimbs(4) 5的含义。递推关系的推导为什么答案是斐波那契数设f(n)表示爬n级楼梯的不同走法数。分析最后一步的动作如果最后一步走了1 级那么此前已经爬完n - 1级对应的走法数为f(n - 1)如果最后一步走了2 级那么此前已经爬完n - 2级对应的走法数为f(n - 2)。由于最后一步不可能同时既走 1 级又走 2 级两个子集互不重叠且覆盖了所有情况因此得到递推式f(n) f(n - 1) f(n - 2)再考察边界条件f(1) 1只有 1 级楼梯唯一走法是直接走 1 级f(2) 22 级楼梯有两种走法11 或直接 2 级。加上f(0) 1站在起点不迈步也是一种空走法作为递推的锚点数列展开为1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...。这正是从第 2 项开始的斐波那契数列——f(n)等于标准斐波那契数列1, 1, 2, 3, 5, ...的第n 1项。同模块的 Challenge 3 Fibonacci Sequence、Challenge 22 Tribonacci Sequence、Challenge 145 Nth Fibonacci Number 都与该递推思想同源可见斐波那契递推是每日挑战模块反复考察的核心模式。官方测试用例用断言锁定的行为规范题目文件的--hints--段落通过 6 组断言精确定义了函数的行为边界覆盖了从小到大、直至大规模输入的取值调用期望返回值getUniqueClimbs(4)5getUniqueClimbs(5)8getUniqueClimbs(10)89getUniqueClimbs(18)4181getUniqueClimbs(29)832040getUniqueClimbs(50)20365011074这些断言直接以可执行代码形式写在题目中例如assert.equal(getUniqueClimbs(4), 5);逐组核对可以发现f(4)5、f(5)8与上面手动展开的数列一致f(10)89是斐波那契第 11 项f(50)20365011074则验证了实现必须支持大规模输入。值得一提的是20365011074仍小于 JavaScript 的Number.MAX_SAFE_INTEGER9007199254740991因此官方测试用例在双精度浮点数范围内可精确表示无需引入BigInt——这与题目要求的普通数值返回类型保持一致。起点代码Seed题目为答题者提供了最小化的起点实现位于--seed--/--seed-contents--段function getUniqueClimbs(steps) { return steps; }这个占位实现仅原样返回steps显然无法通过任何测试。答题者的任务是在保留函数名与参数签名的前提下补全真正的走法统计逻辑。该函数名与签名正是 6 组测试断言所依赖的契约改动函数名或参数将导致断言直接失败。官方题解逐行剖析题目文件--solutions--段给出了官方参考实现采用**迭代动态规划滚动变量**写法function getUniqueClimbs(steps) { if (steps 0) return 0; if (steps 1) return 1; if (steps 2) return 2; let prev2 1, prev1 2; for (let i 3; i steps; i) { [prev2, prev1] [prev1, prev2 prev1]; } return prev1; }逐行解读其设计意图边界处理steps 0返回00 级或负数没有合法走法steps 1返回1steps 2返回2。这三个分支覆盖了递推的初始条件避免进入循环时访问未初始化的变量。状态初始化prev2 1对应f(0)prev1 2对应f(1)若把循环变量从 3 起步则prev2/prev1实际扮演f(i-2)/f(i-1)的角色。滚动迭代循环从i 3推进到steps每次用数组解构赋值[prev2, prev1] [prev1, prev2 prev1]一次性完成「旧值丢弃、新值接替」——prev1更新为prev2 prev1即f(i)同时prev2接住旧的prev1。这个技巧避免了引入临时变量写法紧凑且语义清晰。返回循环结束后prev1恰好是f(steps)。该实现的时间复杂度为O(n)单次线性扫描空间复杂度为O(1)仅两个变量是这道题在面试与刷题语境下的标准最优解。算法演进从朴素递归到迭代官方题解并非唯一路径理解从朴素到优化的演进能加深对动态规划「重叠子问题」本质的认识。朴素递归指数级仅作推导示意直接照搬递推式f(n) f(n-1) f(n-2)会形成指数级调用树例如getUniqueClimbs(50)需要约2^50量级的重复计算实际运行会卡死且容易在递归深度上逼近调用栈上限function getUniqueClimbs(steps) { if (steps 0) return 0; if (steps 1) return 1; if (steps 2) return 2; return getUniqueClimbs(steps - 1) getUniqueClimbs(steps - 2); }记忆化递归自顶向下O(n) 时间用数组缓存已计算的子问题把每个f(i)只算一次时间复杂度降为O(n)但空间仍为O(n)function getUniqueClimbs(steps) { const memo new Array(steps 1).fill(0); memo[1] 1; memo[2] 2; const climb n { if (n 0) return 0; if (memo[n] ! 0) return memo[n]; memo[n] climb(n - 1) climb(n - 2); return memo[n]; }; return climb(steps); }自底向上迭代官方方案由于f(n)只依赖前两个值无需保留整个数组滚动变量把空间压到O(1)。这正是官方题解选择的工程化平衡点代码量小、无递归栈风险、可线性处理到steps 50甚至更大。在仓库中的运行与验证这道题并非孤立的一个 Markdown 文件而是完整「内容生产 — 数据库 — API 分发 — 前端展示」链条中的一环。题目校验仓库的课程测试框架会对--hints--中的断言执行求值。daily-coding-challenges-javascript块配置了disableLoopProtectTests: true同时模块级测试位于 curriculum/src/test/daily-challenges.test.js用于在内容侧验证每日挑战的格式与断言可执行性。种子数据生成每日挑战由脚本 tools/daily-challenges/seed-daily-challenges.ts 从 Dev Playground 超级块经 GraphQL 拉取后写入 MongoDB 的DailyCodingChallenges集合脚本要求 JavaScript 与 Python 两个版本各恰好 365 道对应EXPECTED_CHALLENGE_COUNT 365并以2025-08-11为起点按天递增分配日期详见 tools/daily-challenges/README.md。种子数据中会同时携带该题的测试断言tests与起始代码challengeFiles数据结构由 client/src/utils/daily-coding-challenge-validator.ts 中的 Joi Schema 约束每个语言版本必须包含teststext testString与challengeFilesfileKey contents。API 分发客户端通过公开只读接口获取题目信息路由定义在 api/src/daily-coding-challenge/routes/daily-coding-challenge.ts包括按YYYY-MM-DD查询、按MM-DD查询、/today、按月列表、全部列表与最新日期等端点请求与响应结构由 TypeBox Schema 定义于 api/src/daily-coding-challenge/schemas/daily-coding-challenge.ts。日期处理工具 api/src/daily-coding-challenge/utils/helpers.ts 中实现了dateStringToUtcMidnight、monthDayStringToUtcDate、getSourceDate等函数负责把请求日期映射到 2025-08-11 至 2026-08-10 的原始挑战日期区间含 2 月 29 日映射到 2 月 28 日的闰年处理前端侧对应的日期工具在 client/src/components/daily-coding-challenge/helpers.ts。本地验证在本地克隆仓库后可在任意 Node 环境直接验证题解逻辑——将官方题解与断言复制到脚本中执行或用pnpm运行课程测试套件对daily-coding-challenges-javascript块做整体校验。注意每日挑战题目的在线提交仍走主挑战完成路由见 api/src/daily-coding-challenge/README.md公开 GET 接口仅用于读取题目信息。变体与延伸思考掌握这道题后可以自然迁移到以下变体允许走 1/2/3 级递推变为f(n) f(n-1) f(n-2) f(n-3)边界条件相应扩展滚动变量需要三个最小步数而非走法数问题从计数转为最优化可改用贪心或 DP 求最少步数代价约束每级台阶带权重时需要引入「到第 i 级的最小累计代价」状态输入规模扩展若测试用例逼近或超过Number.MAX_SAFE_INTEGER需切换为BigInt或字符串大数运算这也是同模块 String MathChallenge 249等题目专门考察的方向。从本质上看「Unique Stair Climber」是一道用最小代码量呈现「最优子结构 重叠子问题」两大 DP 特征的入门题官方提供的迭代滚动实现更是把空间复杂度压到常数的教科书范例值得作为复习动态规划时的最小自检用例。【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考