爬楼梯与硬币组合
从头实现经典一维递推
爬楼梯与硬币组合 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
认识爬楼梯问题
每次可以走 1 步或 2 步。走到第 n 级台阶有多少种方案？这个经典的一维 DP其实就是另一种形式的斐波那契数列。
找出递推式
要站在第 i 级台阶上，您可以从第 i-1 级或第 i-2 级走来。因此 dp[i] = dp[i-1] + dp[i-2]，也就是把最后两步的走法相加。
dp[i] = dp[i-1] + dp[i-2]设置边界条件
停在地面有一种方案，到达第 1 级台阶也有一种方案。这些边界条件为整张表提供初始值。
dp[0], dp[1] = 1, 1填表并读取答案
从低到高遍历后，最后一个单元格就保存了方案数。完整解法就是一个很小的递推填表循环。
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]缩减为两个变量
您只需要最后两个值，因此可以去掉数组。这个O(1) 空间的版本是竞赛中最常用的写法。
a, b = 1, 1
for _ in range(n):
a, b = b, a+b切换到硬币组合
给定各种硬币的面值，统计凑出金额 A 的方案数。这里不考虑顺序，因此统计的是组合，而不是序列。
coins = [1, 2, 5]组合表
令 dp[x] 表示凑出 x 的方案数。先设置凑出 0 的一种方案：硬币的空集合。
dp = [0]*(A+1)
dp[0] = 1将硬币循环放在外层
将硬币循环放在金额循环外层。这样的顺序会让每种组合恰好被统计一次，而不会统计排列。
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]组合与排列
交换循环顺序后，统计的就会变成有序方案。仅仅改变循环嵌套顺序，就会改变答案的含义。
零钱兑换的最小值变体
要找最少硬币数时，保存最小值而不是总和。先用无穷大初始化，然后取子问题最优值加 1。
dp[x] = min(dp[x], dp[x-c] + 1)一种模式，多种形式
爬楼梯和硬币问题具有相同的结构：每个状态都会在若干个前置状态中求和或取最小值。识别出这一点后，代码就很容易写出来了。
快速检查
统计硬币组合时，采用什么循环顺序可以避免重复？
回顾：累加最后几步
现在您可以用一维递推式解决爬楼梯和硬币计数问题。每个答案都由若干个更早的状态累加得到，而循环顺序决定统计的是组合还是排列。
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「爬楼梯与硬币组合」课时是免费的吗？
是的 — 「爬楼梯与硬币组合」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「爬楼梯与硬币组合」这节课中我会学到什么？
从头实现经典一维递推 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「爬楼梯与硬币组合」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。