10.3 跳台阶
题目链接
题目描述
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
![](https://img-blog.csdnimg.cn/img_convert/3bfc91dd2650b6060e9f5fdb7fee5bbd.png)
解题思路
当 n = 1 时,只有一种跳法:
![](https://img-blog.csdnimg.cn/img_convert/27c32e43b57a026e89a39bf975d61cd8.png)
当 n = 2 时,有两种跳法:
![](https://img-blog.csdnimg.cn/img_convert/d0e8088abe70dfca263743fc8a55fbaa.png)
跳 n 阶台阶,可以先跳 1 阶台阶,再跳 n-1 阶台阶;或者先跳 2 阶台阶,再跳 n-2 阶台阶。而 n-1 和 n-2 阶台阶的跳法可以看成子问题,该问题的递推公式为:
![](https://img-blog.csdnimg.cn/img_convert/a0b96e604cb666cc1a093355173acca9.jpeg)
public int JumpFloor(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 2; i < n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}