力扣:70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
4. 1 阶 + 1 阶 + 1 阶
5. 1 阶 + 2 阶
6. 2 阶 + 1 阶
分析:此题采用斐波那契解决,可是为什么要采用斐波那契呢?可用运用数学归纳法的思想来考虑,第一步可以走1级台阶,也可以走2级台阶。 那么,设S(n)表示走n级台阶的走法数量,如果第一步走1级台阶,剩下的台阶数为n-1,也就是说这种情况下的走法是相当于S(n-1);同理,如果第一步走2级台阶,剩下的台阶数为n-2,这样的走法相当于S(n-2);于是,得出递推公式:S(n) = S(n-1) + S(n-2);
下面是利用递归实现的代码段
function climbStairs(n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
else {
return climbStairs(n - 1) + climbStairs(n - 2)
}
}
可是这样提交测评的结果会显示超出时间限制
这是改进后的代码段
function climbStairs(n) {
let a = new Array(n);
for (let i = 0; i <= n; i++) {
if (i == 0 || i == 1) {
a[i] = 1;
}
else {
a[i] = a[i - 1] + a[i - 2];
}
}
return a[n];
}
空间优化
function climbStairs(n) {
let n1 = 1;
let n2 = 2;
let temp = 0;
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
else {
for (let i = 3; i <= n; i++) {
temp = n1 + n2;
n1 = n2;
n2 = temp;
}
}
return temp;
}
版权声明:本文为qq_43959230原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。