Count ways to reach the n’th stair in Python

In this tutorial, we’ll learn how to count the number of ways to reach the n’th stair in Python.
We need to reach the top of the staircase which has n steps. At each step, we can climb either 1 or 2 step(s) further. We need to count the number of ways possible to reach the n’th stair.

Explanation:

This problem can be solved using recursion. If we closely look at the problem statement we can figure out that the number of ways to reach n’th stair = Number of ways to reach the (n-1)th stair + Number of ways to reach (n-2)th stair.
If we try to build a recursion tree for this, then we can see that there are overlapping subproblems and optimal substructure. So, an effective solution is to use dynamic programming.

Practical Demonstration:

1. Input the stair we want to reach
2. Initialize a list of size (n+1).
3. The number of ways to reach the 0’th stair is 1.
4. The number of ways to reach the 1’st stair is also 1.
5. Now, based on the formula explained above, the number of ways to reach the 2’nd stair = Number of ways to reach 1’st stair+ Number of ways to reach 0’th stair and so on.
6. At last, we print the value present at the n’th index of our list.

Python program to count the number of ways to reach the n’th stair in Python

# Bottom-up approach (Dynamic Programming)

n=int(input("Enter the stair you want to reach: "))
now=[0]*(n+1)
now[0]=1
now[1]=1
for i in range(2,n+1):
    now[i]=now[i-1]+now[i-2]
print("Number of ways to reach "+str(n)+"th stair are: ",now[n])

 Output:

 Enter the stair you want to reach: 4
 Number of ways to reach 4th stair are: 5


The runtime complexity of above program is O(n).

Recommended Posts:

Print all the Longest Common Subsequences in Lexicographical order in Python

Floyd Warshall Algorithm in Python