# 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 = 2Output: 2Explanation: There are two ways to climb to the top.1. 1 step + 1 step2. 2 steps`

Example 2:

`Input: n = 3Output: 3Explanation: There are three ways to climb to the top.1. 1 step + 1 step + 1 step2. 1 step + 2 steps3. 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.

1. take 1 step at a time
2. take 1 step and then take 2 steps
3. 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.

1. take 1 step at a time
2. 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.

1. 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 —

1. Create an array `steps` with size = n to hold the number of ways you can travel each step in the array.
2. As a base case, if n ≤ 2 we return n for obvious reasons.
3. Initialize `steps = 1` and `steps = 2` as we saw in the example above.
4. We start from the third step until we reach n and calculate the number of ways for each step
5. 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 = 1;    steps = 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

--

--

I am a Software Engineer from India and working in Berlin, Germany. I write about technology, my experiences in Germany, travel in Europe.