leetcode70 Climbing Stairs

 1 """
 2 You are climbing a stair case. It takes n steps to reach to the top.
 3 Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
 4 Note: Given n will be a positive integer.
 5 Example 1:
 6 Input: 2
 7 Output: 2
 8 Explanation: There are two ways to climb to the top.
 9 1. 1 step + 1 step
10 2. 2 steps
11 Example 2:
12 Input: 3
13 Output: 3
14 Explanation: There are three ways to climb to the top.
15 1. 1 step + 1 step + 1 step
16 2. 1 step + 2 steps
17 3. 2 steps + 1 step
18 """
19 """
20 共有三种解法
21 解法一：递归，判题器超时
22 解法二：斐波拉契数列
23 解法三：维护一个数组，循环相加
24 解法二和三的时间复杂度都为O(n)，但解法二的空间复杂度更低。
25 """
26 """
27 解法一：
28 Time Limit Exceeded
29 Last executed input 38
30 """
31 class Solution1:
32     def climbStairs(self, n):
33         if n == 1:
34             return 1
35         if n == 2:
36             return 2
37         return self.climbStairs(n-1) + self.climbStairs(n-2)
38 """
39 解法二
40 """
41 class Solution2:
42     def climbStairs(self, n):
43         if n == 1:
44             return 1
45         if n == 2:
46             return 2
47         first = 1
48         second = 2
49         res = 0
50         for i in range(3, n+1):
51             res = first + second
52             first = second
53             second = res
54         return res
55 """
56 解法三
57 """
58 class Solution3:
59     def climbStairs(self, n):
60         res = [0]*(n+1)
61         if n == 1:
62             return 1
63         if n == 2:
64             return 2
65         res[1] = 1
66         res[2] = 2
67         for i in range(3, n+1):
68             res[i] = res[i-1] + res[i-2]
69         return res[n]