# Climbing Stairs | Leetcode #70 | Easy

In this post I will discuss the solution to the leetcode problem — Climbing Stairs.

## Problem:

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:

This is one of the classic interview problems I have been asked at least 2–3 times so far. Let’s take a small example before diving into the algorithm.

*Let’s say the input is 3 i.e. you have to climb total 3 steps. There are **3 ways** you can do that.*

- take 1 step at a time
- take 1 step and then take 2 steps
- take 2 steps and then take 1 step

*Let’s say the input is 2 i.e. you have to climb total 2 steps. There are **2 ways** you can do that.*

- take 1 step at a time
- take 2 steps in one go

*Let’s say the input is 1 i.e. you have to climb 1 step. There is only **1 way** you can do that.*

- take 1 step

Do you see any pattern in the example above? The number of ways you can climb *n steps* is actually the *sum of* number of ways you can climb *n -1 steps* and number of ways you can climb *n-2 steps*. That is our algorithm to solve this problem. Let’s see how it looks —

- Create an array
`steps`

with size = n to hold the number of ways you can travel each step in the array. - As a base case, if n ≤ 2 we return n for obvious reasons.
- Initialize
`steps[0] = 1`

and`steps[1] = 2`

as we saw in the example above. - We start from the third step until we reach n and calculate the number of ways for each step
- In the end we return
`steps[n — 1]`

as the final output.

`class Solution {`

public int climbStairs(int n) {

int[] steps = new int[n];

if (n <= 2) {

return n;

}

steps[0] = 1;

steps[1] = 2;

for (int i = 2; i < n; i++) {

steps[i] = steps[i - 1] + steps[i - 2];

}

return steps[n - 1];

}

}

I hope you enjoyed solving this problem and the solution helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems