freeCodeCamp 每日编程挑战 252 解析：Unique Stair Climber 爬楼梯问题的斐波那契式动态规划-平芜编程栈

freeCodeCamp 每日编程挑战 252 解析：Unique Stair Climber 爬楼梯问题的斐波那契式动态规划

【免费下载链接】freeCodeCampfreeCodeCamp.org's 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 Finder"，Challenge 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 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 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) = 2：2 级楼梯有两种走法（1+1 或直接 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)`	`5`
`getUniqueClimbs(5)`	`8`
`getUniqueClimbs(10)`	`89`
`getUniqueClimbs(18)`	`4181`
`getUniqueClimbs(29)`	`832040`
`getUniqueClimbs(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_INTEGER（9007199254740991），因此官方测试用例在双精度浮点数范围内可精确表示，无需引入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返回0（0 级或负数没有合法走法）；steps === 1返回1；steps === 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 约束：每个语言版本必须包含tests（text + testString）与challengeFiles（fileKey + 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 Math"（Challenge 249）等题目专门考察的方向。

从本质上看，「Unique Stair Climber」是一道用最小代码量呈现「最优子结构 + 重叠子问题」两大 DP 特征的入门题，官方提供的迭代滚动实现更是把空间复杂度压到常数的教科书范例，值得作为复习动态规划时的最小自检用例。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考