###### tags: `leetcode` `easy` `Math` `Dynamic Programming` `Memoization`
# [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/description/)

## Description

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?

## Examples
### 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 \leq n \leq 45$

## Code

int climbStairs(int n){
    if(n < 3) return n;
    int preOne = 0, preTwo = 1, result = 2;
    for(int i = 2 ; i < n ; i++){
        preOne = preTwo;
        preTwo = result;
        result = preOne + preTwo;
    }
    return result;
}

## Complexity

|Space |Time |
|- |- |
|$O(N)$|$O(N)$|

## Result

- Runtime : 0 ms, 100%
- Memory : 5.4 MB, 95.97%