题目描述

假设一段楼梯15个台阶，小明1步最多能上3个台阶。编写程序计算小明上这段楼梯一共有多少中方法

解题分析

解题思路：从基础情况推导递推公式

确定基础情况（n 较小时的方法数）：

n=1：只有 1 种方法（直接跨 1 阶）→ f (1)=1

n=2：两种方法（1+1、2）→ f (2)=2

n=3：四种方法（1+1+1、1+2、2+1、3）→ f (3)=4

推导递推公式： 对于 n≥4 的情况，

最后一步可以是跨 1 阶、2 阶或 3 阶：

若最后一步跨 1 阶，则前面需完成 n-1 阶，方法数为 f (n-1)

若最后一步跨 2 阶，则前面需完成 n-2 阶，方法数为 f (n-2)

若最后一步跨 3 阶，则前面需完成 n-3 阶，方法数为 f (n-3)

输出格式

一行，一个整数，表示答案。

5768