Railway Station | TCS CodeVita 2020 | C ++ program of 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 ; Driver Code ; Given Input ; Initialize DP table with - 1 ; Function call to count the number of ways to reach the n - th station
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 100000 ] ; 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 ] ; } int main ( ) { int n = 4 ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << findWays ( n ) << " STRNEWLINE " ; }