leetcode-70.爬楼梯
Points
- 斐波那契
- 动态规划
题意
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶示例 3：
输入： 4
输出： 5
解释： 有五种方法可以爬到楼顶。
1. 1 1 1 1
2. 2 1 1
3. 1 2 1
4. 1 1 2
5. 2 2
算法
本题算法思想参考自 https://www.cnblogs.com/k-li/p/5543108.html 精辟！
算一下前几个结果，我们会发现这样的规律 1 2 3 5 8 13 21 34 55 ......
即 cliimbStairs(n) = cliimbStairs(n-1) + cliimbStairs(n-2);
code
最近更新的代码
class Solution {
public:
//递归方法:递归很可能要栈溢出
int jumpFloor1(int n) {
if(n == )
return ;
if(n == )
return ;
if(n == )
return ;
return jumpFloor(n-)+jumpFloor(n-);
}
//非递归版的,运行时间也很快
int jumpFloor(int n)
{
if(n == )
return ;
if(n == )
return ;
if(n == )
return ;
int a = , b = ;
int res;
for(int i=; i<=n; i++)
{
res = a + b;
a = b;
b = res;
}
return res;
}
//如果是一步可以爬2/3级呢
int jumpFloor2_3(int n)
{
if(n <= )
return ;
if(n == )
return ;
if(n == )
return ;
int a = , b = , c = ;
int res = ;
for(int i=; i<=n; i++)
{
res = a + b;
a = b;
b = c;
c = res;
}
return res;
}
};
下面是远古（垃圾）代码
class Solution {
public:
int climbStairs(int n) {
if(n == )
return ;
else if(n == )
return ;
int n1 = , n2 = , ans = ;
for(int i=; i<=n; i++)
{
ans = n1 + n2;
n2 = n1;
n1 = ans;
}
return ans;
}
};
后来重写了一次，精简了一些！（不要用较大数比如50去测试，int 已经爆了。既然给的是int返回值，证明样例较小。）
class Solution {
public:
int climbStairs(int n) {
if(n < )
return n;
long res = ;
int i = , a = , b = ;
while((i++) <= n)
{
res = a + b;
a = b;
b = res;
}
return res;
}
};