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:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


Example 2:

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


## Solutions

### 1. DP-迭代自底向上

注意循环次数是 n-1，不是 n-2。

# Time Complexity: O(n)
# Space Complexity: O(1)
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 0:
return 0
if n == 1:
return 1
fn = 0
fn_2 = 1
fn_1 = 1
for i in range(n-1):
fn = fn_2 + fn_1
fn_2 = fn_1
fn_1 = fn
return fn
# Runtime: 40 ms, faster than 27.63% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.


### 2. DP-递归自顶向下

注意存储：

# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 0:
return 0
if n == 1:
return 1
self.memo = [0 for _ in range(n+1)]
self.memo = 1
self.memo = 1
self.fibonacci(n)
return self.memo[-1]

def fibonacci(self, n: int) -> int:
if n == 0 or n == 1:
return 1

if self.memo[n-1] == 0:
self.memo[n-1] = self.fibonacci(n-1)

if self.memo[n-2] == 0:
self.memo[n-2] = self.fibonacci(n-2)

self.memo[n] = self.memo[n-1] + self.memo[n-2]
return self.memo[n]

# Runtime: 32 ms, faster than 89.69% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.


不够简洁，做进一步简化：

# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
self.memo = [0 for _ in range(n+1)]
self.memo = 1
self.memo = 1
return self.fibonacci(n)

def fibonacci(self, n: int) -> int:
if self.memo[n] == 0:
self.memo[n] = self.fibonacci(n-1) + self.fibonacci(n-2)
return self.memo[n]

# Runtime: 32 ms, faster than 89.69% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.


当然还可以用哈希表做存储，查找起来也相对较快，不要用 List 查找！

# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
self.memo = {0: 1, 1: 1}
return self.fibonacci(n)

def fibonacci(self, n: int) -> int:
if n in self.memo:
return self.memo[n]

self.memo[n-1] = self.fibonacci(n-1)
self.memo[n-2] = self.fibonacci(n-2)
self.memo[n] = self.memo[n-1] + self.memo[n-2]

return self.memo[n]
# Runtime: 36 ms, faster than 67.28% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 14 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.