Count ways to reach Nth Stairs by taking 1 and 2 steps with exactly one 3 step | Function to find the number the number of ways to reach Nth stair ; Array including number of ways that includes 3 ; Array including number of ways that doesn 't includes 3 ; Initially to reach 3 stairs by taking 3 steps can be reached by 1 way ; Loop to find the number the number of ways to reach Nth stair ; Driver Code
def number_of_ways ( n ) : NEW_LINE INDENT includes_3 = [ 0 ] * ( n + 1 ) NEW_LINE not_includes_3 = [ 0 ] * ( n + 1 ) NEW_LINE includes_3 [ 3 ] = 1 NEW_LINE not_includes_3 [ 1 ] = 1 NEW_LINE not_includes_3 [ 2 ] = 2 NEW_LINE not_includes_3 [ 3 ] = 3 NEW_LINE for i in range ( 4 , n + 1 ) : NEW_LINE INDENT includes_3 [ i ] = includes_3 [ i - 1 ] + includes_3 [ i - 2 ] + not_includes_3 [ i - 3 ] NEW_LINE not_includes_3 [ i ] = not_includes_3 [ i - 1 ] + not_includes_3 [ i - 2 ] NEW_LINE DEDENT return includes_3 [ n ] NEW_LINE DEDENT n = 7 NEW_LINE print ( number_of_ways ( n ) ) NEW_LINE