Railway Station | TCS CodeVita 2020 | Dp table for memoization ; Function to count the number of ways to N - th station ; Base Cases ; If current state is already evaluated ; Count ways in which train 1 can be chosen ; Count ways in which train 2 can be chosen ; Count ways in which train 3 can be chosen ; Store the current state ; Return the number of ways ; Driver Code ; Given Input ; Function call to count the number of ways to reach the n - th station
dp = [ - 1 for i in range ( 100000 ) ] NEW_LINE def findWays ( x ) : NEW_LINE INDENT if ( x < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( x == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( x == 1 ) : NEW_LINE INDENT return 2 NEW_LINE DEDENT if ( x == 2 ) : NEW_LINE INDENT return 4 NEW_LINE DEDENT if ( dp [ x ] != - 1 ) : NEW_LINE INDENT return dp [ x ] NEW_LINE DEDENT count = findWays ( x - 1 ) NEW_LINE count += findWays ( x - 2 ) NEW_LINE count += findWays ( x - 3 ) NEW_LINE dp [ x ] = count NEW_LINE return dp [ x ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 NEW_LINE print ( findWays ( n ) ) NEW_LINE DEDENT