前言说明
算法学习，日常刷题记录。
题目连接
题目内容
假设你正在爬楼梯，需要n阶你才能到达楼顶。
每次你可以爬1或2个台阶，你有多少种不同的方法可以爬到楼顶呢？
注意：给定n是一个正整数。
示例1:
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例2:
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
分析过程
先用最直观的归纳法找出前5项的答案，再通过比较寻找规律。
输入： 1
输出： 1
解释： 有一种方法可以爬到楼顶。
- 1 阶
输入： 4
输出： 4
解释： 有五种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶 + 1 阶
1 阶 + 1 阶 + 2 阶
1 阶 + 2 阶 + 1 阶
2 阶 + 1 阶 + 1 阶
2 阶 + 2 阶
输入： 5
输出： 8
解释： 有八种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶
1 阶 + 1 阶 + 1 阶 + 2 阶
1 阶 + 1 阶 + 2 阶 + 1 阶
1 阶 + 2 阶 + 1 阶 + 1 阶
1 阶 + 2 阶 + 2 阶
2 阶 + 1 阶 + 1 阶 + 1 阶
2 阶 + 1 阶 + 2 阶
2 阶 + 2 阶 + 1 阶
加上示例中的输入2、3，可以得到前5个的结果如下：
输入：1、2、3、4、5
输出：1、2、3、5、8
通过比较输入1、2、3、4、5的结果可以发现，其实就是斐波那契数列，f(n) = f(n-1) + f(n-2)。
所以代码如下：
class Solution {
public int climbStairs(int n) {
// 直接调用递归方法
return fibonacci(n);
}
// 递归法
private static int fibonacci(int n) {
if (n == 1 || n == 2) {
return n;
}
// f(n)等于前两个相加
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
但是运行结果如下：
运行提示超时了，当输入n = 45时，运行超时。
因为递归是很耗费时间的，所以这里不能用递归法。
我们可以选择使用迭代法，逐个叠加算出下一个结果。
从1开始往后循环叠加，每次把上一次的结果累加，上一次的结果更新为当前结果，每次加1阶，阶数记为m。
如果阶数m大于等于输入的阶数n，那么结束循环，返回当前结果。
解答代码
所以使用迭代法的代码，如下：
class Solution {
public int climbStairs(int n) {
// 通过比较1、2、3、4、5的结果就能发现，其实就是斐波那契数列，f(n)=f(n-1)+f(n-2)
// n阶：1、2、3、4、5
// 方法：1、2、3、5、8
// 但是直接用递归法解，会超时，当n=45时就已经超时了
// 下面从1开始递增，每次计算出当前结果，当等于n时就结束
// 注意：n=45时，返回的结果已经到了边界值，n=46时，返回的结果已经溢出
// 保存当前结果
int currentTotal = 1;
// 保存上一个结果
int lastTotal = 1;
int m = 1;
// 从1开始递增
while (m < n) {
int temp = currentTotal;
currentTotal += lastTotal;
lastTotal = temp;
++m;
}
return currentTotal;
}
}
提交结果
执行用时0ms，时间击败100.00%的用户，内存消耗35.2MB，空间击败39.10%的用户。
原文链接
原文链接：爬楼梯
