返回题库

兔子爬楼梯

Hopping Rabbit

专题
Probability / 概率
难度
L4

题目详情

一只兔子在 nn 阶楼梯底部，每次只能向上跳 1 阶或 2 阶。

问：兔子到达楼顶共有多少种不同走法？

A rabbit is at the bottom of an nn-step staircase. The rabbit can hop up only 1 or 2 steps at a time. In how many distinct ways can the rabbit reach the top?

解析

设 f(n)f(n) 为到达第 nn 阶的走法数。

  • f(1)=1f(1)=1，f(2)=2f(2)=2。
  • 对 n>2n>2，最后一步要么从 n−1n-1 跳 1 阶，要么从 n−2n-2 跳 2 阶：
f(n)=f(n−1)+f(n−2).f(n)=f(n-1)+f(n-2).

因此是斐波那契型递推。

Original Explanation

Let f(n)f(n) be the number of ways. By induction:

  • f(1)=1f(1) = 1 (just one step).
  • f(2)=2f(2) = 2 (two single steps or one double step).
  • For n>2n>2, the rabbit’s last hop is either 1 step or 2 steps: f(n)  =  f(n−1)  +  f(n−2),f(n) \;=\; f(n-1) \;+\; f(n-2), matching the Fibonacci-type recurrence.