# Climbing Stairs

Published: Dec 12, 2022

Easy Dynamic Programming Memoization

## Problem 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?

Constraints:

• `1 <= n <= 45`

https://leetcode.com/problems/climbing-stairs/

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

## How to Solve

This is a well-known problem. The DP (dynamic programming) and recursion are common approaches. The DP approach can simplify the solution by considering the problem as a fibonacci sequence. The sequence is: step(n) = step(n - 1) + step(n - 2). Starting from two states, previous of previous and previous, repeat adding those gives the answer.

## Solution

``````class ClimbingStairs {
public:
int climbStairs(int n) {
if (n <= 2) { return n; }
int prevprev = 1, prev = 2, cur = 0;
for (auto i = 2; i < n; ++i) {
cur = prevprev + prev;
prevprev = prev;
prev = cur;
}
return cur;
}
};
``````
``````class ClimbingStairs {
public int climbStairs(int n) {
if (n <= 2) { return n; }
int prevprev = 1, prev = 2, cur = 0;
for (int i = 2; i < n; ++i) {
cur = prevprev + prev;
prevprev = prev;
prev= cur;
}
return cur;
}
}
``````
``````/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if (n <= 2) { return n; }
let prevprev = 1, prev = 2, cur = 0;
for (let i = 2; i < n; i++) {
cur = prevprev + prev;
prevprev = prev;
prev = cur;
}
return cur;
};
``````
``````class ClimbingStairs:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
prevprev = 1
prev = 2
cur = 0
for i in range(2, n):
cur = prevprev + prev
prevprev, prev = prev, cur
return cur
``````
``````# @param {Integer} n
# @return {Integer}
def climb_stairs(n)
if n <= 2
return n
end
prevprev, prev, cur = 1, 2, 0
(2...n).each do |_|
cur = prevprev + prev
prevprev = prev
prev = cur
end
return cur
end
``````

## Complexities

• Time: `O(n)`
• Space: `O(1)`