兔子爬楼梯

Rabbit on the Staircase

专题: Discrete Math / 离散数学
难度: L4
来源: Brainstellar

题目详情

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

对 $n=1,2,3,\dots$ ，兔子到达楼顶的不同走法数构成什么数列？

A rabbit sits at the bottom of a staircase with n stairs. The rabbit can hop up only one or two stairs at a time. What kind of sequence is depicted by the different ways possible for the rabbit to ascend to the top of the stairs of length n=1,2,3...?

Hint

Recursion

解析

斐波那契数列。

设 $f(n)$ 为到达第 $n$ 阶的走法数。最后一步要么从 $n-1$ 阶跳 1 阶上来，要么从 $n-2$ 阶跳 2 阶上来，因此

f(n)=f(n-1)+f(n-2),\quad f(0)=f(1)=1.

这正是斐波那契递推。

Original Explanation

Fibonacci Sequence.

Solution

Suppose f(n) are the number of ways to reach nth stair. Notice that the final hop is either a single jump or double jump, i.e. its from (n-1)th stair or (n-2)th. Thus f(n) = f(n-1) + f(n-2), where f(0)=f(1)=1. This is Fibonacci sequence.