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()
T(n) = C + 2C + 4C + ……. + 2n – 1C
= C
T(n) = O() /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]
Total Complexity: O(n) X O(X) /X = number of steps
Space Complexity: O(n) /for storing in the array