CREATE OWN LIBRARY

You are climbing a staircase It takes n steps to reach the top.

Each time you can either climb 1 or 3 or 5 steps. In how many distinct ways you can climb to the top?

Let’s take an example              N stairs taking 1 or 2 steps at a time

Seeing above example we can find a pattern that if we take first one step then total number of ways is calculating among (n – 1) steps or if we take first two steps at once then total number of ways is calculating among (n – 1) steps or if we take first two steps at once then total number of ways in calculating among (n – 2) stairs.

∴ f(n) = f(n – 1) + f(n – 2)

In the example of the question

There are n steps taking 1 or 3 or 5 steps at a time

∴ f(n) = f(n – 1) + f(n – 3) + f(n – 5)

If there are 0 stairs    then ways = 1 {[0]}

Bruteforce Approach

i.e.

Step 1: Define a function which takes parameter ‘n’ as number of stairs

Step 2: if n = 0 or n == 1      

                 return 1         //  i.e. either 0 or 1 stairs return number of ways = 1

            else

                 return num_ways(n – 1) + num_ways(n – 2)          /recursive approach

For example   n = 3

CODE

def num_ways(n)
		if n == 0 or n == 1
			return 1
		else
			return num_ways(n – 1) + num_ways(n – 2)

Using these approaches will take a lot of time.            /Exponentials

Let’s write the recurrence relation for finding time complexity.

T(n) = T(n – 1) + T(n – 2) + O(1)

=O($2^n$)

T(n) = C + 2C + 4C + ……. + 2n – 1C

= C$2^n$

T(n) = O($2^n$)                  /Exponential

If we are careful, we can observe that there is an optimal substructure and overlapping subproblems.

Here we can apply dynamic programming using bottom up approach.

Step 1: Define a function which takes parameter ‘n’ as no. of stairs

Step 2: if n = 0 :           then return 1

Step 3: else

                   Create an array of size (n + 1)           /to store the number of ways for i stairs

Step 4: Initialize the first position of the array with 1

Step 5: Run a loop from index 1 to (n + 1)

Step 6: Initialize a variable total with 0 to store the number of ways for each i in N

Step 7: Run another loop in the length of number of ways asked

Step 8: Using bottom-up approach

             Finding for 1, 2, 3, ……….. stairs

             i in outer for loop and j in the inner for loop

                       if (i – j) ≥ 0

                       then

                       calculate total = total nums[I – j]

Step 9: Run Step 7 and Step 8 until loop finishes

Step 10: Store total at nums[i]

Step 11: Run Step 5 to 10 until loop finshes

Step 12: Return the required nums[n]