StairCase Problem using Recursion & Backtracking (#70 Leetcode)

This is one of the famous problems in dynamic programming or recursion.  This problem falls under Fibonacci Numbers. Fibonacci Numbers is one of the dynamic Programming problem. 

Fibonacci Series is 1, 1, 2, 3, 5, 8, 13, 21, ....

The base condition is F(0) = 0, F(1) = 1

                                      F(n) = F(n-1) + F(n-2) for n >= 2

It is basically the summation of previous two fibonacci numbers in the series. 

Why Fibonacci Numbers is dynamic programming?

If we want to compute the fibonacci number for a random number, we would use decision tree. 

As per the equation, F(5) will be computed by F(4) + F(3) and further F(4) will be computed by summing up F(3) + F(2) until it reaches base cases F(0) or F(1). After computing the left side tree from F(4) to F(1), we will start right tree. But, if we notice the right tree computation is already available at the left side. Then it is not necessary to compute this again. This leads us to dynamic programming. 

Hackerrank Problem Statement

Davis has a number of staircases in his house and he likes to climb each staircase 1, 2, or 3 steps at a time. being a very precocious child, he wonders how many ways there are to reach the top of the staircase. 

Given the respective heights for each of the s staircase in his house, find and print the number of ways he can climb each staircase. 

n = 5

The staircase has 5 steps. Davis can step on the following sequence of steps:

1 1 1 1 1
1 1 1 2
1 1 2 1 
1 2 1 1
2 1 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
2 3 

There are 13 ways to climb to the top.

Leetcode Problem Statement

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

I found two ways to solve this problem: 

1. Recursion 

2. Creative Thinking or Algorithmic Mind

Recursion 

class Solution {
public:
    int climbStairs(int n) {
        int arr[n];
        memset(arr, 0, sizeof(arr));
        int count = distinctWays(arr, 0, n);
        return count;
    }
    
    int distinctWays(int arr[], int index, int n) {
        int count = 0;
        
        if (n < 0) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        
 
        arr[index] = 1;
        count += distinctWays(arr, index+1, n-1);
        

        arr[index] = 2;
        count += distinctWays(arr, index+1, n-2);
        
        return count;
    }
};

The below dry-run of an algorithm was done for example 2 of Leetcode problem. The pink leaflets are the correct solution when n reaches 0. Blue leaflet denotes the incorrect condition. 

This whiteboard visual representation is available here. 

Creative Thinking or Algorithmic Mind 

For n = 1, total number of ways = 1 
For n = 2, total number of ways = 2
For n = 3 total number of ways = 3
For n = 4, total number of ways = 5 = (total number of ways for n=3) + (total number of ways for n = 2)
This is nothing but Fibonacci sequence in which next number is sum of previous two, I hope you get the solution

	class Solution {
	public:
	
	int climbStairs(int n) {
		int a = 1, b = 2;
		if(n == 1)
			return a;
		else if(n == 2)
			return b;
		int c;
		for(int i=3; i<=n; ++i)
			c = a+b, a = b, b = c;
		return c;
	}
};

References : 

Hackerrank

Leetcode