Count ways to reach the Nth station | Function to find the number of ways to reach Nth station ; Declares the DP [ ] array ; Only 1 way to reach station 1 ; Find the remaining states from the 2 nd station ; If the train A is present at station i - 1 ; If the train B is present at station i - 2 ; If train C is present at station i - 3 ; The total number of ways to reach station i ; Return the total count of ways ; Driver Code
def numberOfWays ( N ) : NEW_LINE INDENT DP = [ [ 0 for i in range ( 5 ) ] for i in range ( N + 1 ) ] NEW_LINE DP [ 1 ] [ 1 ] = 1 NEW_LINE DP [ 1 ] [ 2 ] = 1 NEW_LINE DP [ 1 ] [ 3 ] = 1 NEW_LINE DP [ 1 ] [ 4 ] = 1 NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT if ( i - 1 > 0 and DP [ i - 1 ] [ 1 ] > 0 ) : NEW_LINE INDENT DP [ i ] [ 1 ] = DP [ i - 1 ] [ 4 ] NEW_LINE DEDENT if ( i - 2 > 0 and DP [ i - 2 ] [ 2 ] > 0 ) : NEW_LINE INDENT DP [ i ] [ 2 ] = DP [ i - 2 ] [ 4 ] NEW_LINE DEDENT if ( i - 3 > 0 and DP [ i - 3 ] [ 3 ] > 0 ) : NEW_LINE INDENT DP [ i ] [ 3 ] = DP [ i - 3 ] [ 4 ] NEW_LINE DEDENT DP [ i ] [ 4 ] = ( DP [ i ] [ 1 ] + DP [ i ] [ 2 ] + DP [ i ] [ 3 ] ) NEW_LINE DEDENT return DP [ N ] [ 4 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 15 NEW_LINE print ( numberOfWays ( N ) ) NEW_LINE DEDENT