韩槑槑

LeetCode 70 爬楼梯(剑指 offer 矩形覆盖)

字数统计: 281阅读时长: 1 min
2019/01/04 Share

题目

该题在 LeetCode 被称为 爬楼梯
剑指 offer 中被称为 跳台阶
剑指 offer 中的另一道题 矩形覆盖 也可理解为跳台阶

题目要求:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

解题思路

n 阶跳法的结果是 f(n)
假设第一次跳了 1 阶,那么还剩下 n - 1 个台阶
假设第一次跳了 2 阶,那么还剩下 n - 2 个台阶
f(n) = f(n - 1) + f(n - 2)

这里跳1还是跳2都不算是一种跳法,最终的结果是从这两个分支到终点才算一种跳法,因此这里的1或2跟后面的跳法是一个整体,所以 f(n) = f(n - 1) + f(n - 2)

根据题意又知道 f(1) = 1f(2) = 2
其实就是一个 斐波那契数列

1
2
3
4
5
6
7
8
9
10
public class Solution {
public int JumpFloor(int target) {
if (target < 2) {
return 1;
}
int sum_1 = JumpFloor(target - 1);
int sum_2 = JumpFloor(target - 2);
return sum_1 + sum_2;
}
}
CATALOG
  1. 1. 题目
  2. 2. 解题思路