Railway Station | TCS CodeVita 2020 | Java program for the above approach ; 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 ; Driven Code ; Given Input ; Initialize DP table with - 1 ; Function call to count the number of ways to reach the n - th station
import java . util . * ; class GFG { static int dp [ ] = new int [ 100000 ] ; static int findWays ( int x ) { if ( x < 0 ) return 0 ; if ( x == 0 ) return 1 ; if ( x == 1 ) return 2 ; if ( x == 2 ) return 4 ; if ( dp [ x ] != - 1 ) return dp [ x ] ; int count = findWays ( x - 1 ) ; count += findWays ( x - 2 ) ; count += findWays ( x - 3 ) ; dp [ x ] = count ; return dp [ x ] ; } public static void main ( String [ ] args ) { int n = 4 ; Arrays . fill ( dp , - 1 ) ; System . out . print ( findWays ( n ) ) ; } }