经典问题：跳台阶
题目描述
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
在这里插入图片描述
解题思路
当 n = 1 时，只有一种跳法：
在这里插入图片描述
当 n = 2 时，有两种跳法：
在这里插入图片描述
跳 n 阶台阶，可以先跳 1 阶台阶，再跳 n-1 阶台阶；或者先跳 2 阶台阶，再跳 n-2 阶台阶。而 n-1 和 n-2 阶台阶的跳法可以看成子问题，该问题的递推公式为：
在这里插入图片描述
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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-12-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录