70. Climbing Stairs
Tags
- Dynamic Programming
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
题意：
你在爬楼梯。到达山顶需要N步。 每次你可以爬上1或2个步骤。你有多少种不同的方法可以爬到山顶？
分析：
题目意思很简单，就是求出1和2组合相加等于n的方法总数，这个其实跟斐波那契数列问题类似。因此，本题做法都大同小异，递归和动态规划都可以，只要找到其中的规律就可以了。
思路：
根据分析，我们可以很容易找到规律：f(n) = f(n - 1) + f(n - 2); 唯一的不同点在于采用什么方式来提升效率，节省空间了。
复杂度
时间复杂度O(n)
Js实现
方法 #1
let climbStairs = function(n) {
if (n < 4) return n;
let a = 2, b = 3, c = 5;
for (let i = 5; i <= n; i++)
{
a = c;
c = b+c;
b = a;
}
return c;
};
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
方法 #2
let climbStairs = function(n) {
let f1 = 2;
let f2 = 1;
if(n == 1) {
return f2;
} else if(n == 2) {
return f1;
}
let fn;
for(let i = 3; i <= n; i++) {
fn = f1 + f2;
f2 = f1;
f1 = fn;
}
return fn;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
方法 #3
let climbStairs = function(n) {
//动态规划
let res = [];
res[0] = 1;
res[1] = 1;
for (let i = 2; i <= n; i++)
{
res[i%3] = res[(i-1)%3] + res[(i-2)%3];
}
return res[n%3];
};
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11