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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution(object):
# Top down - TLE
def climbStairs1(self, n):
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n-1)+self.climbStairs(n-2)
# Top down + memorization (dictionary)
def __init__(self):
self.dic = {1:1, 2:2}
def climbStairs(self, n):
if n not in self.dic:
self.dic[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
return self.dic[n]
# Bottom up, O(n) space
def climbStairs2(self, n):
if n == 1:
return 1
res = [0 for i in xrange(n)]
res[0], res[1] = 1, 2
for i in xrange(2, n):
res[i] = res[i-1] + res[i-2]
return res[-1]
# Bottom up, constant space
def climbStairs3(self, n):
if n == 1:
return 1
a, b = 1, 2
for i in xrange(2, n):
tmp = b
b = a+b
a = tmp
return b
# Top down + memorization (list)
def climbStairs4(self, n):
if n == 1:
return 1
dic = [-1 for i in xrange(n)]
dic[0], dic[1] = 1, 2
return self.helper(n-1, dic)
def helper(self, n, dic):
if dic[n] < 0:
dic[n] = self.helper(n-1, dic)+self.helper(n-2, dic)
return dic[n]

点评

第一个和第二个,递归的做法很容易理解,第二种做法,有用一个字典来做缓存