Count ways to reach the Nth stair using multiple 1 or 2 steps and a single step 3 | Python3 implementation to find the number the number of ways to reach Nth stair by taking 1 or 2 steps at a time and 3 rd Step exactly once ; Function to find the number of ways ; Base Case ; Count of 2 - steps ; Count of 1 - steps ; Initial length of sequence ; expected count of 2 - steps ; Loop to find the ways for every possible sequence ; Driver Code
import math NEW_LINE def ways ( n ) : NEW_LINE INDENT if n < 3 : NEW_LINE INDENT return 0 NEW_LINE DEDENT c2 = 0 NEW_LINE c1 = n - 3 NEW_LINE l = c1 + 1 NEW_LINE s = 0 NEW_LINE exp_c2 = c1 / 2 NEW_LINE while exp_c2 >= c2 : NEW_LINE INDENT f1 = math . factorial ( l ) NEW_LINE f2 = math . factorial ( c1 ) NEW_LINE f3 = math . factorial ( c2 ) NEW_LINE s += f1 // ( f2 * f3 ) NEW_LINE c2 += 1 NEW_LINE c1 -= 2 NEW_LINE l -= 1 NEW_LINE DEDENT return s NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 7 NEW_LINE print ( ways ( N ) ) NEW_LINE DEDENT