导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 递归
    2. 非递归

LeetCode-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?

翻译

有一个n阶的楼梯,每次你爬1或2阶,共有多少种不同的方法爬到顶?

实际为斐波那契数列。到达n层台阶,有两种方法:从n-1爬一阶,或从n-2爬两阶。

递归

1
2
3
4
5
6
7
public class Solution {
public int climbStairs(int n) {
if (n == 1 || n == 2)
return n;
return climbStairs(n - 1) + climbStairs(n - 2);
}
}

但当n = 44时,报Time Limit Exceeded。
循环求第n个斐波那契数。

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int climbStairs(int n) {
if (n == 1 || n == 2)
return n;
int first = 1, second = 2, current = 0;
for (int i = 2; i < n; i++) {
current = first + second;
first = second;
second = current;
}
return current;
}
}

参考:
http://www.tuicool.com/articles/EVFn6f