Hello and welcome to day 3 of the daily Leetcode grind! Today's problem is a refreshingly simple one. It can be perceived as one of the most basic dynamic programming problems. So, if you manage to solve and understand this one, you can proudly brag that you've started your dynamic programming journey!

Let's take a look at the problem first.

Pretty simple, right?

Understanding The Problem

Given a single integer n, which represents the number of steps to reach the top of a staircase, we need to find the number of distinct ways we can climb to the top. The restriction is that we can only take either 1 or 2 steps at a time.

One thing to notice here is that the amount of information given is next to nothing. Just one integer, n. But, do we really need anything else?

The first thing that should come to your mind when such a problem presents itself is to try and break it into smaller parts. This problem would be much less scary if we were told that n could only take values 1 and 2, right?

Intuition

Once we start breaking down the problem, everything starts coming together.

Try to perform a dry run before moving on to the next paragraph. Try to observe a pattern in the answers you obtain from the dry run. If you do find the pattern, try to write up the code for it instead of going through the solution.

Let's do a dry run, shall we? What is the number of distinct ways to climb up a staircase while only taking 1 or 2 steps at a time when:

• n = 0. Though this value of n is outside of the given range, it'll help in identifying the pattern. The answer to this problem for n = 0 will be 0; there can't be any distinct way to climb up a staircase if there are no stairs.

• n = 1. Obviously, there is only one way to climb up 1 stair, hence the answer is 1.

• n = 2. Here, there are two ways of reaching the top. First, we directly take 2 steps and reach the top. And second, we take one step twice and reach the top.

• n = 3. There are three ways of reaching the top of the staircase here.

  1. 1 + 1 +1

  2. 2 + 1

  3. 1 + 2

• n = 4. Five ways to reach the top in this case.

  1. 1 + 1 + 1 + 1

  2. 2 + 2

  3. 2 + 1 + 1

  4. 1 + 2 + 1

  5. 1 + 1 + 2

The values that follow these will be 8 (for n = 5), 13 (for n =6) and so on.

Can you see the pattern yet? Write down these values in a row and observe them carefully.

0,1,2,3,5,8,13... and so on.

This is nothing but the Fibonacci sequence! The value of the ith (for i > 3) term in a Fibonacci sequence is given by:

$$t{i} = t{i-1} + t_{i-2}$$

So, the solution to this problem will be just to calculate the nth term of the Fibonacci series. That value will be the number of distinct ways to climb up a staircase with n steps.

Coding Up The Steps

There are multiple ways to calculate the nth term of the Fibonacci series. I'll be discussing the most efficient method: dynamic programming with memoization.

In this method, we will maintain an array fib[n+1] that will store the intermediate results for us. That is, fib[i] will store the number of distinct ways to climb up a staircase with i steps.

The following code achieves the same:

int climbStairs(int n){
        if(n==1 || n==2) return n;
        int fib[n+1];
        fib[0] = 0,fib[1] = 1,fib[2] = 2;
        for(int i = 3;i<=n;i++){
            fib[i] = fib[i-1] + fib[i-2];
        }
        return fib[n];
}

We initialize the first three terms of the array as 0,1 and 2. To calculate the rest of the terms, we run a loop from 3 to n and assign the value fib[i-1] + fib[i-2] to fib[i]. The final answer will be stored in the last term of the array.

That's it for today! Hope you had fun with this problem. If you'd like a challenge, try to solve the same problem with recursion and memoization.

Do come back tomorrow for the solution to the next problem.

Cheers!