# Count ways to reach the Nth station

Count ways to reach the Nth stationGiven N stations and three trains A, B, and C such that train A stops at every station, train B stops at every second station, and train C stops at every third station, the task is to find the number of ways to reach the Nth station can be reached from station 1.Examples:Input: N = 4Output: 3Explanation:Below are the ways of reaching station 4 from station 1 as follows:Take train A at station 1 and continue to station 4 using only train A as (A → A → A → A).Take train B at station 1, stop at station 3 and take train A from station 3 to 4 as (B→ . → A).Take train C from station 1 and stop at station 4(C→ .)Therefore, the total number of ways to reach station 4 from station 1 is 3.Input: N = 15Output: 338Approach: The given problem can be solved using the following observations:Train A can be used to reach station X only if train A reaches X – 1.Train B can be used to reach station X only if train B reaches X – 2.Train C can be used to reach station X only if train C reaches X – 3.Therefore, from the above observations, the idea is to use the concept of Dynamic Programming. Follow the steps given below to solve the problem:Initialize a 2D array DP such that:DP[i] stores the number of ways to reach station i using train A.DP[i] stores the number of ways to reach station i using train B.DP[i] stores the number of ways to reach station i using train C.DP[i] stores the number of ways to reach station i using trains A, B, or C.There is only one way of reaching station 1. Therefore, update the value of DP, DP, DP, DP as 1.Using the above observations, update the value of each state by iterating the loop as follows:DP[i] = DP[i-1]DP[i] = DP[i-2]DP[i] = DP[i-3]DP[i] = DP[i] + DP[i] + DP[i]After completing the above steps, print the value of DP[N] as the result.Below is the implementation of the above approach:C++#include using namespace std;int numberOfWays(int N){        int DP[N + 1];        memset(DP, 0, sizeof(DP));        DP = 1;    DP = 1;    DP = 1;    DP = 1;            for (int i = 2; i 0 && DP[i – 1] > 0)            DP[i] = DP[i – 1];                        if (i – 2 > 0 && DP[i – 2] > 0)            DP[i] = DP[i – 2];                        if (i – 3 > 0 && DP[i – 3] > 0)            DP[i] = DP[i – 3];                        DP[i] = (DP[i] + DP[i]                    + DP[i]);    }        return DP[N];}int main(){    int N = 15;    cout 0 and DP[i – 1] > 0):            DP[i] = DP[i – 1]                        if (i – 2 > 0 and DP[i – 2] > 0):            DP[i] = DP[i – 2]                        if (i – 3 > 0 and DP[i – 3] > 0):            DP[i] = DP[i – 3]                        DP[i] = (DP[i] + DP[i] + DP[i])        return DP[N]if __name__ == ‘__main__’:         N = 15         print(numberOfWays(N))Output: 338Time Complexity: O(N)Auxiliary Space: O(N)Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course. 