70. Climbing Stairs

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?

**Note:** Given *n* will be a positive integer.

**Example 1:**

1
2
3
4
5
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
**Example 2:**
1
2
3
4
5
6
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
思路:看着很眼熟,斐波那契数列,用递归法做,简单~
1
2
3
4
5
6
7
8
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
};
结果提示超时,网上解释:递归程序太慢,像斐波那契问题,重复计算了很多分支,使用动态规划法填表,提高效率,程序也简单。代码如下:
1
2
3
4
5
6
7
8
9
10
11
int climbStairs(int n)
{
vector<int> res(n+1);
res[0] = 1;
res[1] = 1;
for (int i = 2; i <= n; i++)
{
res[i] = res[i-1] + res[i-2];
}
return res[n];
}
动态规划法用熟了,高手就需要节省空间,如下:
1
2
3
4
5
6
7
8
9
10
11
int climbStairs2(int n)
{
vector<int> res(3);
res[0] = 1;
res[1] = 1;
for (int 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
12
13
//2014-2-10 update
int climbStairs(int n)
{
if (n < 4) return n;
int a = 2, b = 3, c = 5;
for (int i = 5; i <= n; i++)
{
a = c;
c = b+c;
b = a;
}
return c;
}
Res. 0 ms, Ranking 100.100%,效果十分喜人。