🐰😺📐 兔猫信奥学院·加菲老师的楼梯攀登之旅 📐🐰😺

在一个阳光明媚的早晨，加菲老师带着小兔和小猫来到信奥学院旁的古老石阶前。
“同学们，”加菲老师微笑着说，“今天我们来做一个简单而有趣的练习：假设你们需要爬上这 $n$ 阶石阶，每一步可以跨 1 阶或 2 阶，你们一共有多少种不同的方式能到达顶端呢？”

故事说完，下面正式进入信息学奥赛® 题目。

输入格式

输入只有一行，包含一个整数 n，表示楼梯的总台阶数。

• $1 \le n \le 45$

输出格式

输出一个整数，表示有多少种不同的方法可以爬到楼顶。

2

2

• 当 $n=2$ 时，有两种方法：
  1. $1+1$
  2. $2$

3

3

• 当 $n=3$ 时，有三种方法：
  1. $1+1+1$
  2. $1+2$
  3. $2+1$

🎓 加菲老师寄语：
通过这个简单的楼梯攀登问题，同学们可以初步体会到动态规划（DP）的思想：将大问题拆解成子问题，利用状态转移快速求解。后续我们会在更复杂的场景中继续运用这一宝贵方法。

祝大家学习进步，爬阶不停！