### 70.Climbing Stairs

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``````

### Analyze

• 到达当前的台阶的方法有两种:
• 一种方法是从`上一级台阶加一`;
• 另一种方法是从`上上一级台阶加二`;

• 记忆化递归方法:
``````const arr = [1, 2]

/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
if (n === 1) return arr[0]
if (n === 2) return arr[1]

if (arr[n]) return arr[n]
arr[n] = climbStairs(n - 1) + climbStairs(n - 2)
return arr[n]
}``````
``````/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
const arr = [1, 2]
for (let i = 2; i < n; i++) {
arr[i] = arr[i - 1] + arr[i - 2]
}

return arr[n - 1]
}``````