AMC8 2010

AMC8 2010 · Q25

AMC8 2010 · Q25. It mainly tests Recursion & DP style counting (basic).

Every day at school, Jo climbs a flight of 6 stairs. Jo can take stairs 1, 2, or 3 at a time. For example, Jo could climb 3, then 1, then 2 stairs. In how many ways can Jo climb the stairs?

Jo 每天上学要爬一段 6 级楼梯。Jo 可以一次迈 1、2 或 3 级台阶。例如，Jo 可以爬 3 级，然后 1 级，然后 2 级。Jo 有多少种方法爬楼梯？

(A) 13 13

(B) 18 18

(D) 22 22

(E) 24 24

Answer

Correct choice: (E)

正确答案：（E）

Solution

A dynamics programming approach is quick and easy. The number of ways to climb one stair is $1$. There are $2$ ways to climb two stairs: $1$,$1$ or $2$. For 3 stairs, there are $4$ ways: ($1$,$1$,$1$) ($1$,$2$) ($2$,$1$) ($3$) For four stairs, consider what step they came from to land on the fourth stair. They could have hopped straight from the 1st, done a double from #2, or used a single step from #3. The ways to get to each of these steps are $1+2+4=7$ ways to get to step 4. The pattern can then be extended: $4$ steps: $1+2+4=7$ ways. $5$ steps: $2+4+7=13$ ways. $6$ steps: $4+7+13=24$ ways. Thus, there are $\boxed{\textbf{(E) } 24}$ ways to get to step $6.$

使用动态规划方法。1 级楼梯：1 种。2 级：2 种（1+1 或 2）。3 级：4 种（1+1+1、1+2、2+1、3）。 4 级：从前一级、两级、三级而来，1+2+4=7 种。 5 级：2+4+7=13 种。 6 级：4+7+13=24 种。因此，到达第 6 级有 $\boxed{\textbf{(E) } 24}$ 种方法。

Topics

CP.009 Recursion & DP style counting (basic)