# 70.climbing-stairs

## Statement

• Difficulty: Easy
• Tag: `记忆化搜索` `数学` `动态规划`

``````输入：n = 2

1. 1 阶 + 1 阶
2. 2 阶``````

``````输入：n = 3

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
``````

• `1 <= n <= 45`

• Difficulty: Easy
• Tag: `Memoization` `Math` `Dynamic Programming`

You are climbing a staircase. It takes `n` steps to reach the top.

Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top?

Example 1:

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

Example 2:

``````Input: n = 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
``````

Constraints:

• `1 <= n <= 45`

## Solution

``````class Solution:
f = {}

def dfs(self, n: int) -> int:
if n < 0:
return 0
if n == 0:
return 1

if n not in self.f.keys():
self.f[n] = self.dfs(n - 1) + self.dfs(n - 2)

return self.f[n]

def climbStairs(self, n: int) -> int:
return self.dfs(n)
``````