LeetCode 题解工作台
到达第 K 级台阶的方案数
给你有一个 非负 整数 k 。有一个无限长度的台阶， 最低 一层编号为 0 。 Alice 有一个整数 jump ，一开始值为 0 。Alice 从台阶 1 开始，可以使用 任意 次操作，目标是到达第 k 级台阶。假设 Alice 位于台阶 i ，一次 操作 中，Alice 可以： 向下走一级到 i…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $\textit{dfs}(i, j, \textit{jump})$，表示当前位于第 级台阶，且进行了 次操作 和 次操作 ，到达第 级台阶的方案数。那么答案就是 $\textit{dfs}(1, 0, 0)$。 函数 $\textit{dfs}(i, j, \textit{jump})$ 的计算过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。
Alice 有一个整数 jump ，一开始值为 0 。Alice 从台阶 1 开始，可以使用 任意 次操作，目标是到达第 k 级台阶。假设 Alice 位于台阶 i ，一次 操作 中，Alice 可以：
- 向下走一级到
i - 1，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。 - 向上走到台阶
i + 2jump处，然后jump变为jump + 1。
请你返回 Alice 到达台阶 k 处的总方案数。
注意，Alice 可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。
示例 1：
输入：k = 0
输出：2
解释：
2 种到达台阶 0 的方案为：
- Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
示例 2：
输入：k = 1
输出：4
解释：
4 种到达台阶 1 的方案为：
- Alice 从台阶 1 开始，已经到达台阶 1 。
- Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- Alice 从台阶 1 开始。
- 执行第二种操作，向上走 20 级台阶到台阶 2 。
- 执行第一种操作，向下走 1 级台阶到台阶 1 。
- Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- 执行第一种操作，向下走 1 级台阶到台阶 0 。
- 执行第二种操作，向上走 21 级台阶到台阶 2 。
- 执行第一种操作，向下走 1 级台阶到台阶 1 。
提示：
0 <= k <= 109
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示当前位于第 级台阶，且进行了 次操作 和 次操作 ，到达第 级台阶的方案数。那么答案就是 。
函数 的计算过程如下：
- 如果 ，由于无法连续两次向下走，所以无法再到达第 级台阶，返回 ；
- 如果 ，表示已经到达第 级台阶，答案初始化为 ，然后继续计算；
- 如果 且 ，表示可以向下走，递归计算 ；
- 递归计算 ，累加到答案中。
为了避免重复计算，我们使用记忆化搜索，将已经计算过的状态保存起来。
时间复杂度 ，空间复杂度 。
class Solution:
def waysToReachStair(self, k: int) -> int:
@cache
def dfs(i: int, j: int, jump: int) -> int:
if i > k + 1:
return 0
ans = int(i == k)
if i > 0 and j == 0:
ans += dfs(i - 1, 1, jump)
ans += dfs(i + (1 << jump), 0, jump + 1)
return ans
return dfs(1, 0, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on whether you use naive recursion, memoized recursion, or iterative DP with combinatorial counting. Naive recursion can be exponential, memoization reduces it to O(k^2), and optimized combinatorial DP can approach O(k) space and time under constraints. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate models state transitions correctly for both operation types.
- question_mark
Notice if combinatorial reasoning is applied to reduce redundant paths.
- question_mark
Observe how edge cases like k = 0 or negative intermediate stairs are handled.
常见陷阱
外企场景- error
Failing to memoize or track states, leading to exponential recursion.
- error
Miscounting sequences when combining two operation types in different orders.
- error
Ignoring edge cases such as reaching stair 0 or negative indices.
进阶变体
外企场景- arrow_right_alt
Limit the number of operations allowed and count only sequences within the limit.
- arrow_right_alt
Include stair constraints where certain stairs cannot be stepped on.
- arrow_right_alt
Extend to multiple players with independent sequences interacting on the same staircase.